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