Given a Binary Tree. The task is to print the number of set bits in each of the nodes in the Binary Tree.
The idea is to traverse the given binary tree using any tree traversal method, and for each node calculate the number of set bits and print it.
Note: One can also use the __builtin_popcount() function available in C++ to directly count the number of set bits in an integer.
Below is the implementation of the above approach:
C++
// CPP program to print the number of set bits// in each node of the binary tree#include <bits/stdc++.h>using namespace std;// Binary Tree nodestruct Node { int data; struct Node *left, *right;};// Utility function that allocates a new NodeNode* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node);}// Function to print the number of set bits// in each node of the binary treevoid printSetBit(Node* root){ if (root == NULL) return; // Print the number of set bits of // current node using __builtin_popcount() cout << "Set bits in Node " << root->data << " = " << __builtin_popcount(root->data) << "\n"; // Traverse Left Subtree printSetBit(root->left); // Traverse Right Subtree printSetBit(root->right);}// Driver codeint main(){ Node* root = newNode(16); root->left = newNode(13); root->left->left = newNode(14); root->left->right = newNode(12); root->right = newNode(11); root->right->left = newNode(10); root->right->right = newNode(16); printSetBit(root); return 0;} |
Java
// Java program to print the number of set bits// in each node of the binary treeimport java.util.*;class GFG {// Binary Tree nodestatic class Node { int data; Node left, right;};// Utility function that allocates a new Nodestatic Node newNode(int data){ Node node = new Node(); node.data = data; node.left = node.right = null; return (node);}// Function to print the number of set bits// in each node of the binary treestatic void printSetBit(Node root){ if (root == null) return; // Print the number of set bits of // current node using __builtin_popcount() System.out.print("Set bits in Node " + root.data + " = " + Integer.bitCount(root.data) + "\n"); // Traverse Left Subtree printSetBit(root.left); // Traverse Right Subtree printSetBit(root.right);}// Driver codepublic static void main(String[] args) { Node root = newNode(16); root.left = newNode(13); root.left.left = newNode(14); root.left.right = newNode(12); root.right = newNode(11); root.right.left = newNode(10); root.right.right = newNode(16); printSetBit(root);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to print the number of set bits# in each node of the binary tree# Binary Tree nodeclass Node: def __init__(self): self.data = None self.left = None self.right = None# Utility function that allocates a new Nodedef newNode(data): node = Node() node.data = data node.left = None node.right = None return node# Function to print the number of set bits# in each node of the binary treedef printSetBit(root: Node): if root is None: return # Print the number of set bits of # current node using count() print("Set bits in Node %d = %d" % (root.data, bin(root.data).count('1'))) # Traverse Left Subtree printSetBit(root.left) # Traverse Right Subtree printSetBit(root.right)# Driver Codeif __name__ == "__main__": root = newNode(16) root.left = newNode(13) root.left.left = newNode(14) root.left.right = newNode(12) root.right = newNode(11) root.right.left = newNode(10) root.right.right = newNode(16) printSetBit(root)# This code is contributed by# sanjeev2552 |
C#
// C# program to print the number of set bits// in each node of the binary treeusing System; class GFG {// Binary Tree nodepublic class Node { public int data; public Node left, right;};// Utility function that allocates a new Nodestatic Node newNode(int data){ Node node = new Node(); node.data = data; node.left = node.right = null; return (node);}// Function to print the number of set bits// in each node of the binary treestatic void printSetBit(Node root){ if (root == null) return; // Print the number of set bits of // current node using __builtin_popcount() Console.Write("Set bits in Node " + root.data + " = " + bitCount(root.data) + "\n"); // Traverse Left Subtree printSetBit(root.left); // Traverse Right Subtree printSetBit(root.right);}static int bitCount(int x){ int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;} // Driver codepublic static void Main(String[] args) { Node root = newNode(16); root.left = newNode(13); root.left.left = newNode(14); root.left.right = newNode(12); root.right = newNode(11); root.right.left = newNode(10); root.right.right = newNode(16); printSetBit(root);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to print the number // of set bits in each node of the binary tree// A Binary Tree Nodeclass Node{ constructor(data) { this.left = null; this.right = null; this.data = data; }}// Utility function that allocates a new Nodefunction newNode(data){ let node = new Node(data); return (node);}function bitCount(x){ let setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;} // Function to print the number of set bits// in each node of the binary treefunction printSetBit(root){ if (root == null) return; // Print the number of set bits of // current node using __builtin_popcount() document.write("Set bits in Node " + root.data + " = " + bitCount(root.data) + "</br>"); // Traverse Left Subtree printSetBit(root.left); // Traverse Right Subtree printSetBit(root.right);}// Driver codelet root = newNode(16);root.left = newNode(13);root.left.left = newNode(14);root.left.right = newNode(12);root.right = newNode(11);root.right.left = newNode(10);root.right.right = newNode(16);printSetBit(root);// This code is contributed by suresh07</script> |
Output
Set bits in Node 16 = 1 Set bits in Node 13 = 3 Set bits in Node 14 = 3 Set bits in Node 12 = 2 Set bits in Node 11 = 3 Set bits in Node 10 = 2 Set bits in Node 16 = 1
Time Complexity: O(N × log2(max_node)), where N is the number of nodes, and max_node is the node with the maximum value.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
