Find the level with maximum setbit count in given Binary Tree
Given a binary tree having N nodes, the task is to find the level having the maximum number of setbits.
Note: If two levels have same number of setbits print the one which has less no of nodes. If nodes are equal print the first level from top to bottom
Examples:
Input:
2
/ \
5 3
/ \
6 1
Output: 2
Explanation: Level 1 has only one setbit => 2 (010).
Level 2 has 4 setbits. => 5 (101) + 3 (011).
Level 3 has 3 setbits. => 6 (110) +1 (001).Input:
2
/ \
5 3
/ \ \
6 1 8
Output: 2
Approach: The problem can be solved using level order traversal itself. Find the number of setbits in each level and the level having the maximum number of setbits following the given condition in the problem. Follow the steps mentioned below:
- Use the level order traversal and for each level:
- Find the total number of setbits in each level.
- Update the maximum setbits in a level and the level having the maximum number of setbits.
- Return the level with maximum setbits.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Structure of a binary tree node struct Node { int data; struct Node *left, *right; }; // Function to count no of set bit int countSetBit( int x) { int c = 0; while (x) { int l = x % 10; if (x & 1) c++; x /= 2; } return c; } // Function to convert tree element // by count of set bit they have void convert(Node* root) { if (!root) return ; root->data = countSetBit(root->data); convert(root->left); convert(root->right); } // Function to get level with max set bit int printLevel(Node* root) { // Base Case if (root == NULL) return 0; // Replace tree elements by // count of set bits they contain convert(root); // Create an empty queue queue<Node*> q; int currLevel = 0, ma = INT_MIN; int prev = 0, ans = 0; // Enqueue Root and initialize height q.push(root); // Loop to implement level order traversal while (q.empty() == false ) { // Print front of queue and // remove it from queue int size = q.size(); currLevel++; int totalSet = 0, nodeCount = 0; while (size--) { Node* node = q.front(); // Add all the set bit // in the current level totalSet += node->data; q.pop(); // Enqueue left child if (node->left != NULL) q.push(node->left); // Enqueue right child if (node->right != NULL) q.push(node->right); // Count current level node nodeCount++; } // Update the ans when needed if (ma < totalSet) { ma = totalSet; ans = currLevel; } // If two level have same set bit // one with less node become ans else if (ma == totalSet && prev > nodeCount) { ma = totalSet; ans = currLevel; prev = nodeCount; } // Assign prev = // current level node count // We can use it for further levels // When 2 level have // same set bit count // print level with less node prev = nodeCount; } return ans; } // Utility function to create new tree node Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver program int main() { // Binary tree as shown in example Node* root = newNode(2); root->left = newNode(5); root->right = newNode(3); root->left->left = newNode(6); root->left->right = newNode(1); root->right->right = newNode(8); // Function call cout << printLevel(root) << endl; return 0; } |
Java
// Java code to implement the above approach import java.util.*; class GFG{ // Structure of a binary tree node static class Node { int data; Node left, right; }; // Function to count no of set bit static int countSetBit( int x) { int c = 0 ; while (x!= 0 ) { int l = x % 10 ; if (x% 2 == 1 ) c++; x /= 2 ; } return c; } // Function to convert tree element // by count of set bit they have static void convert(Node root) { if (root== null ) return ; root.data = countSetBit(root.data); convert(root.left); convert(root.right); } // Function to get level with max set bit static int printLevel(Node root) { // Base Case if (root == null ) return 0 ; // Replace tree elements by // count of set bits they contain convert(root); // Create an empty queue Queue<Node> q = new LinkedList<>(); int currLevel = 0 , ma = Integer.MIN_VALUE; int prev = 0 , ans = 0 ; // Enqueue Root and initialize height q.add(root); // Loop to implement level order traversal while (q.isEmpty() == false ) { // Print front of queue and // remove it from queue int size = q.size(); currLevel++; int totalSet = 0 , nodeCount = 0 ; while (size-- > 0 ) { Node node = q.peek(); // Add all the set bit // in the current level totalSet += node.data; q.remove(); // Enqueue left child if (node.left != null ) q.add(node.left); // Enqueue right child if (node.right != null ) q.add(node.right); // Count current level node nodeCount++; } // Update the ans when needed if (ma < totalSet) { ma = totalSet; ans = currLevel; } // If two level have same set bit // one with less node become ans else if (ma == totalSet && prev > nodeCount) { ma = totalSet; ans = currLevel; prev = nodeCount; } // Assign prev = // current level node count // We can use it for further levels // When 2 level have // same set bit count // print level with less node prev = nodeCount; } return ans; } // Utility function to create new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Driver program public static void main(String[] args) { // Binary tree as shown in example Node root = newNode( 2 ); root.left = newNode( 5 ); root.right = newNode( 3 ); root.left.left = newNode( 6 ); root.left.right = newNode( 1 ); root.right.right = newNode( 8 ); // Function call System.out.print(printLevel(root) + "\n" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach # Structure of a binary Tree node import sys class Node: def __init__( self ,d): self .data = d self .left = None self .right = None # Function to count no of set bit def countSetBit(x): c = 0 while (x): l = x % 10 if (x & 1 ): c + = 1 x = (x / / 2 ) return c # Function to convert tree element # by count of set bit they have def convert(root): if (root = = None ): return root.data = countSetBit(root.data) convert(root.left) convert(root.right) # Function to get level with max set bit def printLevel(root): # Base Case if (root = = None ): return 0 # Replace tree elements by # count of set bits they contain convert(root) # Create an empty queue q = [] currLevel,ma = 0 , - sys.maxsize - 1 prev,ans = 0 , 0 # Enqueue Root and initialize height q.append(root) # Loop to implement level order traversal while ( len (q) ! = 0 ): # Print front of queue and # remove it from queue size = len (q) currLevel + = 1 totalSet,nodeCount = 0 , 0 while (size): node = q[ 0 ] q = q[ 1 :] # Add all the set bit # in the current level totalSet + = node.data # Enqueue left child if (node.left ! = None ): q.append(node.left) # Enqueue right child if (node.right ! = None ): q.append(node.right) # Count current level node nodeCount + = 1 size - = 1 # Update the ans when needed if (ma < totalSet): ma = totalSet ans = currLevel # If two level have same set bit # one with less node become ans elif (ma = = totalSet and prev > nodeCount): ma = totalSet ans = currLevel prev = nodeCount # Assign prev = # current level node count # We can use it for further levels # When 2 level have # same set bit count # print level with less node prev = nodeCount return ans # Driver program # Binary tree as shown in example root = Node( 2 ) root.left = Node( 5 ) root.right = Node( 3 ) root.left.left = Node( 6 ) root.left.right = Node( 1 ) root.right.right = Node( 8 ) # Function call print (printLevel(root)) # This code is contributed by shinjanpatra |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; public class GFG{ // Structure of a binary tree node class Node { public int data; public Node left, right; }; // Function to count no of set bit static int countSetBit( int x) { int c = 0; while (x!=0) { int l = x % 10; if (x%2==1) c++; x /= 2; } return c; } // Function to convert tree element // by count of set bit they have static void convert(Node root) { if (root== null ) return ; root.data = countSetBit(root.data); convert(root.left); convert(root.right); } // Function to get level with max set bit static int printLevel(Node root) { // Base Case if (root == null ) return 0; // Replace tree elements by // count of set bits they contain convert(root); // Create an empty queue Queue<Node> q = new Queue<Node>(); int currLevel = 0, ma = int .MinValue; int prev = 0, ans = 0; // Enqueue Root and initialize height q.Enqueue(root); // Loop to implement level order traversal while (q.Count!=0 ) { // Print front of queue and // remove it from queue int size = q.Count; currLevel++; int totalSet = 0, nodeCount = 0; while (size-- >0) { Node node = q.Peek(); // Add all the set bit // in the current level totalSet += node.data; q.Dequeue(); // Enqueue left child if (node.left != null ) q.Enqueue(node.left); // Enqueue right child if (node.right != null ) q.Enqueue(node.right); // Count current level node nodeCount++; } // Update the ans when needed if (ma < totalSet) { ma = totalSet; ans = currLevel; } // If two level have same set bit // one with less node become ans else if (ma == totalSet && prev > nodeCount) { ma = totalSet; ans = currLevel; prev = nodeCount; } // Assign prev = // current level node count // We can use it for further levels // When 2 level have // same set bit count // print level with less node prev = nodeCount; } return ans; } // Utility function to create new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Driver program public static void Main(String[] args) { // Binary tree as shown in example Node root = newNode(2); root.left = newNode(5); root.right = newNode(3); root.left.left = newNode(6); root.left.right = newNode(1); root.right.right = newNode(8); // Function call Console.Write(printLevel(root) + "\n" ); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Structure of a binary Tree node class Node { constructor(d) { this .data = d; this .left = null ; this .right = null ; } }; // Function to count no of set bit function countSetBit(x) { let c = 0; while (x) { let l = x % 10; if (x & 1) c++; x = Math.floor(x / 2); } return c; } // Function to convert tree element // by count of set bit they have function convert(root) { if (root == null ) return ; root.data = countSetBit(root.data); convert(root.left); convert(root.right); } // Function to get level with max set bit function printLevel(root) { // Base Case if (root == null ) return 0; // Replace tree elements by // count of set bits they contain convert(root); // Create an empty queue let q = []; let currLevel = 0, ma = Number.MIN_VALUE; let prev = 0, ans = 0; // Enqueue Root and initialize height q.push(root); // Loop to implement level order traversal while (q.length != 0) { // Print front of queue and // remove it from queue let size = q.length; currLevel++; let totalSet = 0, nodeCount = 0; while (size--) { let node = q.shift(); // Add all the set bit // in the current level totalSet += node.data; q.pop(); // Enqueue left child if (node.left != null ) q.push(node.left); // Enqueue right child if (node.right != null ) q.push(node.right); // Count current level node nodeCount++; } // Update the ans when needed if (ma < totalSet) { ma = totalSet; ans = currLevel; } // If two level have same set bit // one with less node become ans else if (ma == totalSet && prev > nodeCount) { ma = totalSet; ans = currLevel; prev = nodeCount; } // Assign prev = // current level node count // We can use it for further levels // When 2 level have // same set bit count // print level with less node prev = nodeCount; } return ans; } // Driver program // Binary tree as shown in example let root = new Node(2); root.left = new Node(5); root.right = new Node(3); root.left.left = new Node(6); root.left.right = new Node(1); root.right.right = new Node(8); // Function call document.write(printLevel(root) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: (N * D) where D is no of bit an element have
Auxiliary Space: O(N)
Contact Us