Saturday, 16 Oct 2021

# Sum of Bitwise AND of the sum of all leaf and non-leaf nodes for each level of a Binary Tree

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                         7Output: 5Explanation:

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   3Output: 1Explanation: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:

Python3

class TreeNode:

def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right

def findSum(root):

que = [root]

ans = 0

while (len(que)):

leaf = 0

nonleaf = 0

length = len(que)

while length:

temp = que.pop(0)

if not temp.left and not temp.right:

leaf += temp.val

else:
nonleaf += temp.val

if temp.left:
que.append(temp.left)
if temp.right:
que.append(temp.right)

length -= 1

ans += leaf & nonleaf

return ans

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)

print(findSum(root))

Time Complexity: O(N)Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.