Level with maximum number of nodes
Last Updated :
20 Feb, 2023
Find the level in a binary tree that has the maximum number of nodes. The root is at level 0.
Examples:
Input:
Output : 2
Explanation:
Input:
Output:1
Explanation
Approach: It is known 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.
BFS traversal is an algorithm for traversing or searching tree or graphs . It starts at the tree root , and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
So at any point the queue of BFS will contain elements of adjacent layers. So this makes the algorithm perfect for this problem.
Algorithm:
- Create the tree, a queue to store the nodes and insert the root in the queue. Create variables level=0,count =0 and level_no=-1
- The implementation will be slightly different, all the elements of same level will be removed in a single iteration.
- Run a loop while size of queue is greater than 0. Get the size of queue (size) and store it. If size is greater than count then update count = size and level_no = level.
- Now run a loop size times, and pop one node from the queue and insert its childrens (if present).
- Increment level.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int maxNodeLevel(Node *root)
{
if (root == NULL)
return -1;
queue<Node *> q;
q.push(root);
int level = 0;
int max = INT_MIN;
int level_no = 0;
while (1)
{
int NodeCount = q.size();
if (NodeCount == 0)
break;
if (NodeCount > max)
{
max = NodeCount;
level_no = 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--;
}
level++;
}
return level_no;
}
int main()
{
struct Node *root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(8);
root->left->right->left = newNode(5);
printf("Level having maximum number of Nodes : %d",
maxNodeLevel(root));
return 0;
}
|
Java
import java.util.*;
class GfG {
static class Node
{
int data;
Node left;
Node right;
}
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return(node);
}
static int maxNodeLevel(Node root)
{
if (root == null)
return -1;
Queue<Node> q = new LinkedList<Node> ();
q.add(root);
int level = 0;
int max = Integer.MIN_VALUE;
int level_no = 0;
while (true)
{
int NodeCount = q.size();
if (NodeCount == 0)
break;
if (NodeCount > max)
{
max = NodeCount;
level_no = 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--;
}
level++;
}
return level_no;
}
public static void main(String[] args)
{
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(8);
root.left.right.left = newNode(5);
System.out.println("Level having maximum number of Nodes : " + maxNodeLevel(root));
}
}
|
Python3
from queue import Queue
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def maxNodeLevel(root):
if (root == None):
return -1
q = Queue()
q.put(root)
level = 0
Max = -999999999999
level_no = 0
while (1):
NodeCount = q.qsize()
if (NodeCount == 0):
break
if (NodeCount > Max):
Max = NodeCount
level_no = 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
level += 1
return level_no
if __name__ == '__main__':
root = newNode(2)
root.left = newNode(1)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(6)
root.right.right = newNode(8)
root.left.right.left = newNode(5)
print("Level having Maximum number of Nodes : ",
maxNodeLevel(root))
|
C#
using System;
using System.Collections.Generic;
public class GfG
{
public class Node
{
public int data;
public Node left;
public Node right;
}
public static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
public static int maxNodeLevel(Node root)
{
if (root == null)
{
return -1;
}
LinkedList<Node> q = new LinkedList<Node> ();
q.AddLast(root);
int level = 0;
int max = int.MinValue;
int level_no = 0;
while (true)
{
int NodeCount = q.Count;
if (NodeCount == 0)
{
break;
}
if (NodeCount > max)
{
max = NodeCount;
level_no = 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--;
}
level++;
}
return level_no;
}
public static void Main(string[] args)
{
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(8);
root.left.right.left = newNode(5);
Console.WriteLine("Level having maximum number of Nodes : " + maxNodeLevel(root));
}
}
|
Javascript
<script>
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
function maxNodeLevel(root)
{
if (root == null)
{
return -1;
}
var q = [];
q.push(root);
var level = 0;
var max = -1000000000;
var level_no = 0;
while (true)
{
var NodeCount = q.length;
if (NodeCount == 0)
{
break;
}
if (NodeCount > max)
{
max = NodeCount;
level_no = level;
}
while (NodeCount > 0)
{
var Node = q[0];
q.shift();
if (Node.left != null)
{
q.push(Node.left);
}
if (Node.right != null)
{
q.push(Node.right);
}
NodeCount--;
}
level++;
}
return level_no;
}
var root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(8);
root.left.right.left = newNode(5);
document.write("Level having maximum number of Nodes : " + maxNodeLevel(root));
</script>
|
Output
Level having maximum number of Nodes : 2
Time Complexity: O(n), In BFS traversal every node is visited only once, So Time Complexity is O(n).
Auxiliary Space: O(n), The space is required to store the nodes in a queue.
An approach using DFS:
Iterate over the tree and for every nodes in the tree, count the frequency of nodes at particular height or depth.
- Create a map for counting the frequency of nodes at a particular height or depth.
- Iterate over the tree
- Increment the count of the number of nodes at a particular depth for every node.
- Iterate over the map and find the level that has the maximum number of nodes.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void dfs(Node* root,unordered_map<int, int> &unmap, int depth){
if(root == NULL) return;
unmap[depth]++;
dfs(root->left,unmap, depth + 1);
dfs(root->right, unmap, depth + 1);
}
int maxNodeLevel(Node *root)
{
unordered_map<int, int> unmap;
dfs(root, unmap, 0);
int maxx = INT_MIN, result;
for(auto it : unmap){
if(it.second > maxx){
result = it.first;
maxx = it.second;
}
else if(it.second == maxx){
result = min(result, it.first);
}
}
return result;
}
int main()
{
struct Node *root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(6);
root->right->right = newNode(8);
root->left->right->left = newNode(5);
printf("Level having maximum number of Nodes : %d",
maxNodeLevel(root));
return 0;
}
|
Java
import java.util.*;
class GFG{
static class Node{
int data;
Node left;
Node right;
}
static Node newNode(int data){
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
static void dfs(Node root, Map<Integer, Integer> unmap, int depth){
if(root == null) return;
if(unmap.containsKey(depth)){
unmap.put(depth, unmap.get(depth)+1);
}else{
unmap.put(depth, 1);
}
dfs(root.left, unmap, depth+1);
dfs(root.right, unmap, depth+1);
}
static int maxNodeLevel(Node root){
Map<Integer, Integer> unmap = new HashMap<Integer, Integer>();
dfs(root, unmap, 0);
int maxx = Integer.MIN_VALUE;
int result = 0;
for(Integer i : unmap.keySet()){
if(unmap.get(i) > maxx){
result = i;
maxx = unmap.get(i);
}
else if(unmap.get(i) == maxx){
result = Math.min(result, i);
}
}
return result;
}
public static void main(String[] args)
{
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(8);
root.left.right.left = newNode(5);
System.out.println("Level having maximum number of Nodes : " + maxNodeLevel(root));
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def dfs(root, unmap, depth):
if root is None:
return
unmap[depth] = unmap.get(depth, 0) + 1
dfs(root.left, unmap, depth + 1)
dfs(root.right, unmap, depth + 1)
def maxNodeLevel(root):
unmap = {}
dfs(root, unmap, 0)
maxx = float('-inf')
result = None
for k, v in unmap.items():
if v > maxx:
result = k
maxx = v
elif v == maxx:
result = min(result, k)
return result
if __name__ == "__main__":
root = Node(2)
root.left = Node(1)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(6)
root.right.right = Node(8)
root.left.right.left = Node(5)
print("Level having maximum number of Nodes:", maxNodeLevel(root))
|
Javascript
class Node{
constructor(data){
this.data = data;
this.left = null;
this.right = null;
}
}
function newNode(data){
let node = new Node(data);
return node;
}
function dfs(root, unmap, depth){
if(root == null) return;
if(unmap.has(depth))
unmap.set(depth, unmap.get(depth)+1);
else
unmap.set(depth, 1);
dfs(root.left, unmap, depth+1);
dfs(root.right, unmap, depth+1);
}
function maxNodeLevel(root){
let unmap = new Map();
dfs(root, unmap, 0);
let maxx = Number.MIN_VALUE;
let result;
unmap.forEach(function(value, key){
if(value > maxx){
result = key;
maxx = value;
}else if(value == maxx){
result = Math.min(result, key);
}
})
return result;
}
let root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(6);
root.right.right = newNode(8);
root.left.right.left = newNode(5);
console.log("Level having maximum number of Nodes : " + maxNodeLevel(root));
|
C#
using System;
using System.Collections.Generic;
public class GFG
{
public class Node
{
public int data;
public Node left;
public Node right;
}
public static Node NewNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
public static void Dfs(Node root, Dictionary<int, int> unmap, int depth)
{
if (root == null)
{
return;
}
if (unmap.ContainsKey(depth))
{
unmap[depth]++;
}
else
{
unmap.Add(depth, 1);
}
Dfs(root.left, unmap, depth + 1);
Dfs(root.right, unmap, depth + 1);
}
public static int MaxNodeLevel(Node root)
{
Dictionary<int, int> unmap = new Dictionary<int, int>();
Dfs(root, unmap, 0);
int maxx = int.MinValue;
int result = 0;
foreach (int i in unmap.Keys)
{
if (unmap[i] > maxx)
{
result = i;
maxx = unmap[i];
}
else if (unmap[i] == maxx)
{
result = Math.Min(result, i);
}
}
return result;
}
public static void Main(string[] args)
{
Node root = NewNode(2);
root.left = NewNode(1);
root.right = NewNode(3);
root.left.left = NewNode(4);
root.left.right = NewNode(6);
root.right.right = NewNode(8);
root.left.right.left = NewNode(5);
Console.WriteLine("Level having maximum number of Nodes: " + MaxNodeLevel(root));
}
}
|
Output
Level having maximum number of Nodes : 2
Time Complexity: O(n), where n is the number of nodes in the given tree.
Auxiliary Space: O(h), where h is the height of the tree, this space is due to the recursion call stack.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...