Sum of Bitwise AND of the sum of all leaf and non-leaf nodes for each level of a Binary Tree
Given a Binary Tree consisting of N nodes, the task is to find the sum of Bitwise AND of the sum of all leaf nodes and the sum of all non-leaf nodes for each level in the given Tree.
Examples:
Input: Below is the given tree:
5
/ \
3 9
/ \
6 4
\
7
Output: 5
Explanation:For Level 1: leaf node sum = 0, non-leaf node sum = 5. So, 0&5 = 0.
For Level 2: leaf node sum = 9, non-leaf node sum = 3. So, 9&3 = 1.
For Level 3: leaf node sum = 4, non-leaf node sum = 6. So, 6&4 = 4.
For Level 4: leaf node sum = 7, non-leaf node sum = 0. So, 0&7 = 0.
Hence, the total sum is 0 + 1 + 4 + 0 = 5.Input: Below is the given tree:
4
/ \
9 3
/ \
5 3
Output: 1
Explanation:
For Level 1: leaf node sum = 0, non-leaf node sum = 4. So, 0&4 = 0
For Level 2: leaf node sum = 9, non-leaf node sum = 3. So, 9&3 = 1
For Level 3: leaf node sum = 8, non-leaf node sum = 0. So, 8&0 = 0
Hence, the total sum is 0 + 1 + 0 = 1
Approach: The idea to solve the above problem is to perform the Level Order Traversal of the tree. While doing traversal, process nodes of different levels separately and for every level being processed, find the sum of leaf nodes and non-leaf nodes for each level. Follow the steps below to solve the problem:
- Initialize a queue Q and push the root node to it and initialize ans as 0 to store the required answer.
- Perform the following steps till Q is not empty:
- Initialize leafSum as 0 and nonLeafSum as 0 to store the sum of leaf nodes and non-leaf nodes at the current level respectively.
- Find the current size of the queue Q and let it be L.
- Iterate over the range [0, L] and do the following:
- Pop the node from the queue.
- If the popped node is a leaf node, then add the value to leafSum else add it to nonLeafSum.
- Push the left and right child of the current popped node into the queue if they exist.
- For the current level add the Bitwise AND of leafSum and nonLeafSum to the variable ans.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for given approach #include<bits/stdc++.h> using namespace std; // Structure of a Binary tree node struct TreeNode { int val; TreeNode *left,*right; // Helper function to allocate // a new node with the given data // and left and right pointers as None TreeNode( int x = 0) { val = x; left = NULL; right = NULL; } }; // Function to calculate the sum of // bitwise AND of the sum of all leaf // nodes and non-leaf nodes for each level int findSum(TreeNode *root){ // Initialize a queue and // append root to it queue<TreeNode*> que; que.push(root); // Store the required answer int ans = 0; while (que.size()) { // Stores the sum of leaf nodes // at the current level int leaf = 0; // Stores the sum of non-leaf // nodes at the current level int nonleaf = 0; // Get the size of the queue int length = que.size(); // Iterate for all the nodes // in the queue currently while (length) { // Dequeue a node from queue auto temp = que.front(); que.pop(); // Check if the node is a // leaf node if (!temp->left && !temp->right) // If true, update the // leaf node sum leaf += temp->val; // Otherwise, update the // non-leaf node sum else nonleaf += temp->val; // Enqueue left and right // children of removed node if (temp->left) que.push(temp->left); if (temp->right) que.push(temp->right); length -= 1; } // Update the answer ans += leaf & nonleaf; } // Return the answer return ans; } // Driver Code int main() { // Given Tree TreeNode *root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(9); root->left->left = new TreeNode(6); root->left->right = new TreeNode(4); root->left->left->right = new TreeNode(7); // Function Call cout<<findSum(root); } // This code is contributed by mohit kumar 29. |
Java
// Java program for given approach import java.util.*; class GFG { // Structure of a Binary tree node static class TreeNode { int val; TreeNode left,right; // Helper function to allocate // a new node with the given data // and left and right pointers as None TreeNode( int x) { val = x; left = null ; right = null ; } }; // Function to calculate the sum of // bitwise AND of the sum of all leaf // nodes and non-leaf nodes for each level static int findSum(TreeNode root) { // Initialize a queue and // append root to it Queue<TreeNode> que = new LinkedList<>(); que.add(root); // Store the required answer int ans = 0 ; while (que.size() > 0 ) { // Stores the sum of leaf nodes // at the current level int leaf = 0 ; // Stores the sum of non-leaf // nodes at the current level int nonleaf = 0 ; // Get the size of the queue int length = que.size(); // Iterate for all the nodes // in the queue currently while (length> 0 ) { // Dequeue a node from queue TreeNode temp = que.peek(); que.remove(); // Check if the node is a // leaf node if (temp.left == null && temp.right == null ) // If true, update the // leaf node sum leaf += temp.val; // Otherwise, update the // non-leaf node sum else nonleaf += temp.val; // Enqueue left and right // children of removed node if (temp.left != null ) que.add(temp.left); if (temp.right != null ) que.add(temp.right); length -= 1 ; } // Update the answer ans += leaf & nonleaf; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given Tree TreeNode root = new TreeNode( 5 ); root.left = new TreeNode( 3 ); root.right = new TreeNode( 9 ); root.left.left = new TreeNode( 6 ); root.left.right = new TreeNode( 4 ); root.left.left.right = new TreeNode( 7 ); // Function Call System.out.print(findSum(root)); } } // This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach # Structure of a Binary tree node class TreeNode: # Helper function to allocate # a new node with the given data # and left and right pointers as None def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right # Function to calculate the sum of # bitwise AND of the sum of all leaf # nodes and non-leaf nodes for each level def findSum(root): # Initialize a queue and # append root to it que = [root] # Store the required answer ans = 0 while ( len (que)): # Stores the sum of leaf nodes # at the current level leaf = 0 # Stores the sum of non-leaf # nodes at the current level nonleaf = 0 # Get the size of the queue length = len (que) # Iterate for all the nodes # in the queue currently while length: # Dequeue a node from queue temp = que.pop( 0 ) # Check if the node is a # leaf node if not temp.left and not temp.right: # If true, update the # leaf node sum leaf + = temp.val # Otherwise, update the # non-leaf node sum else : nonleaf + = temp.val # Enqueue left and right # children of removed node if temp.left: que.append(temp.left) if temp.right: que.append(temp.right) length - = 1 # Update the answer ans + = leaf & nonleaf # Return the answer return ans # Driver Code # Given Tree root = TreeNode( 5 ) root.left = TreeNode( 3 ) root.right = TreeNode( 9 ) root.left.left = TreeNode( 6 ) root.left.right = TreeNode( 4 ) root.left.left.right = TreeNode( 7 ) # Function Call print (findSum(root)) |
C#
// C# program for given approach using System; using System.Collections.Generic; // Structure of a Binary tree node class GFG{ class TreeNode { public int val; public TreeNode left,right; }; // Helper function to allocate // a new node with the given data // and left and right pointers as None static TreeNode newNode( int x) { TreeNode temp = new TreeNode(); temp.val = x; temp.left = null ; temp.right = null ; return temp; } // Function to calculate the sum of // bitwise AND of the sum of all leaf // nodes and non-leaf nodes for each level static int findSum(TreeNode root){ // Initialize a queue and // append root to it Queue<TreeNode> que = new Queue<TreeNode>(); que.Enqueue(root); // Store the required answer int ans = 0; while (que.Count>0) { // Stores the sum of leaf nodes // at the current level int leaf = 0; // Stores the sum of non-leaf // nodes at the current level int nonleaf = 0; // Get the size of the queue int length = que.Count; // Iterate for all the nodes // in the queue currently while (length>0) { // Dequeue a node from queue TreeNode temp = que.Peek(); que.Dequeue(); // Check if the node is a // leaf node if (temp.left == null && temp.right== null ) // If true, update the // leaf node sum leaf += temp.val; // Otherwise, update the // non-leaf node sum else nonleaf += temp.val; // Enqueue left and right // children of removed node if (temp.left!= null ) que.Enqueue(temp.left); if (temp.right != null ) que.Enqueue(temp.right); length -= 1; } // Update the answer ans += (leaf & nonleaf); } // Return the answer return ans; } // Driver Code public static void Main() { // Given Tree TreeNode root = newNode(5); root.left = newNode(3); root.right = newNode(9); root.left.left = newNode(6); root.left.right = newNode(4); root.left.left.right = newNode(7); // Function Call Console.WriteLine(findSum(root)); } } // This code is contributed by bgangwar59. |
Javascript
<script> // Javascript program for given approach // Structure of a Binary tree node class TreeNode { // Helper function to allocate // a new node with the given data // and left and right pointers as None constructor(x) { this .val = x; this .left = null ; this .right = null ; } } // Function to calculate the sum of // bitwise AND of the sum of all leaf // nodes and non-leaf nodes for each level function findSum(root) { // Initialize a queue and // append root to it let que = []; que.push(root); // Store the required answer let ans = 0; while (que.length > 0) { // Stores the sum of leaf nodes // at the current level let leaf = 0; // Stores the sum of non-leaf // nodes at the current level let nonleaf = 0; // Get the size of the queue let length = que.length; // Iterate for all the nodes // in the queue currently while (length > 0) { // Dequeue a node from queue let temp = que.shift(); // Check if the node is a // leaf node if (temp.left == null && temp.right == null ) // If true, update the // leaf node sum leaf += temp.val; // Otherwise, update the // non-leaf node sum else nonleaf += temp.val; // Enqueue left and right // children of removed node if (temp.left != null ) que.push(temp.left); if (temp.right != null ) que.push(temp.right); length -= 1; } // Update the answer ans += leaf & nonleaf; } // Return the answer return ans; } // Driver Code // Given Tree let root = new TreeNode(5); root.left = new TreeNode(3); root.right = new TreeNode(9); root.left.left = new TreeNode(6); root.left.right = new TreeNode(4); root.left.left.right = new TreeNode(7); // Function Call document.write(findSum(root)); // This code is contributed by unknown2108 </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(N)