Find the level in a binary tree which has maximum number of nodes. The root is at level 0.
Examples:
Input :
2
/
1 3
/
4 6 8
/
5
Output : 2
2
/
1 3
/
4 6 8 [Level with maximum nodes = 3]
/
5
We know that in level order traversal of binary tree with queue, at any time our queue contains all elements of a particular level. So find level with maximum number of nodes in queue.
C++
// C++ implementation to find the level // having maximum number of Nodes #include <bits/stdc++.h> using namespace std; /* A binary tree Node has data, pointer to left child and a pointer to right child */struct Node { int data; struct Node* left; struct Node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */struct Node* newNode(int data) { struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return(node); } // function to find the level // having maximum number of Nodes int maxNodeLevel(Node *root) { if (root == NULL) return -1; queue<Node *> q; q.push(root); // Current level int level = 0; // Maximum Nodes at same level int max = INT_MIN; // Level having maximum Nodes int level_no = 0; while (1) { // Count Nodes in a level int NodeCount = q.size(); if (NodeCount == 0) break; // If it is maximum till now // Update level_no to current level if (NodeCount > max) { max = NodeCount; level_no = level; } // Pop complete current level while (NodeCount > 0) { Node *Node = q.front(); q.pop(); if (Node->left != NULL) q.push(Node->left); if (Node->right != NULL) q.push(Node->right); NodeCount--; } // Increment for next level level++; } return level_no; } // Driver program to test above int main() { // binary tree formation struct Node *root = newNode(2); /* 2 */ root->left = newNode(1); /* / */ root->right = newNode(3); /* 1 3 */ root->left->left = newNode(4); /* / */ root->left->right = newNode(6); /* 4 6 8 */ root->right->right = newNode(8); /* / */ root->left->right->left = newNode(5);/* 5 */ printf("Level having maximum number of Nodes : %d", maxNodeLevel(root)); return 0; } |
Java
// Java implementation to find the level // having maximum number of Nodes import java.util.*; class GfG { /* A binary tree Node has data, pointer to left child and a pointer to right child */static class Node { int data; Node left; Node right; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return(node); } // function to find the level // having maximum number of Nodes static int maxNodeLevel(Node root) { if (root == null) return -1; Queue<Node> q = new LinkedList<Node> (); q.add(root); // Current level int level = 0; // Maximum Nodes at same level int max = Integer.MIN_VALUE; // Level having maximum Nodes int level_no = 0; while (true) { // Count Nodes in a level int NodeCount = q.size(); if (NodeCount == 0) break; // If it is maximum till now // Update level_no to current level if (NodeCount > max) { max = NodeCount; level_no = level; } // Pop complete current level while (NodeCount > 0) { Node Node = q.peek(); q.remove(); if (Node.left != null) q.add(Node.left); if (Node.right != null) q.add(Node.right); NodeCount--; } // Increment for next level level++; } return level_no; } // Driver program to test above public static void main(String[] args) { // binary tree formation Node root = newNode(2); /* 2 */ root.left = newNode(1); /* / */ root.right = newNode(3); /* 1 3 */ root.left.left = newNode(4); /* / */ root.left.right = newNode(6); /* 4 6 8 */ root.right.right = newNode(8); /* / */ root.left.right.left = newNode(5);/* 5 */ System.out.println("Level having maximum number of Nodes : " + maxNodeLevel(root)); } } |
Python3
# Python3 implementation to find the # level having Maximum number of Nodes # Importing Queue from queue import Queue # Helper class that allocates a new # node with the given data and None # left and right pointers. class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # function to find the level # having Maximum number of Nodes def maxNodeLevel(root): if (root == None): return -1 q = Queue() q.put(root) # Current level level = 0 # Maximum Nodes at same level Max = -999999999999 # Level having Maximum Nodes level_no = 0 while (1): # Count Nodes in a level NodeCount = q.qsize() if (NodeCount == 0): break # If it is Maximum till now # Update level_no to current level if (NodeCount > Max): Max = NodeCount level_no = level # Pop complete current level while (NodeCount > 0): Node = q.queue[0] q.get() if (Node.left != None): q.put(Node.left) if (Node.right != None): q.put(Node.right) NodeCount -= 1 # Increment for next level level += 1 return level_no # Driver Code if __name__ == '__main__': # binary tree formation root = newNode(2) # 2 root.left = newNode(1) # / root.right = newNode(3) # 1 3 root.left.left = newNode(4) # / root.left.right = newNode(6) # 4 6 8 root.right.right = newNode(8) # / root.left.right.left = newNode(5)# 5 print("Level having Maximum number of Nodes : ", maxNodeLevel(root)) # This code is contributed by Pranchalk |
C#
using System; using System.Collections.Generic; // C# implementation to find the level // having maximum number of Nodes public class GfG { /* A binary tree Node has data, pointer to left child and a pointer to right child */public class Node { public int data; public Node left; public Node right; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */public static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = null; node.right = null; return (node); } // function to find the level // having maximum number of Nodes public static int maxNodeLevel(Node root) { if (root == null) { return -1; } LinkedList<Node> q = new LinkedList<Node> (); q.AddLast(root); // Current level int level = 0; // Maximum Nodes at same level int max = int.MinValue; // Level having maximum Nodes int level_no = 0; while (true) { // Count Nodes in a level int NodeCount = q.Count; if (NodeCount == 0) { break; } // If it is maximum till now // Update level_no to current level if (NodeCount > max) { max = NodeCount; level_no = level; } // Pop complete current level while (NodeCount > 0) { Node Node = q.First.Value; q.RemoveFirst(); if (Node.left != null) { q.AddLast(Node.left); } if (Node.right != null) { q.AddLast(Node.right); } NodeCount--; } // Increment for next level level++; } return level_no; } // Driver program to test above public static void Main(string[] args) { // binary tree formation Node root = newNode(2); // 2 root.left = newNode(1); // / root.right = newNode(3); // 1 3 root.left.left = newNode(4); // / root.left.right = newNode(6); // 4 6 8 root.right.right = newNode(8); // / root.left.right.left = newNode(5); // 5 Console.WriteLine("Level having maximum number of Nodes : " + maxNodeLevel(root)); } } // This code is contributed by Shrikant13 |
Output:
Level having maximum number of nodes : 2
Time Complexity : O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments