Python | Check sum of Covered and Uncovered nodes of Binary Tree
In this solution, we are going to see how to check sum of Covered and Uncovered nodes of Binary Tree in Python programming.
What is the covered and uncovered node?
In a binary tree, any node which appears either on the left border or on the right border are called Uncovered nodes and except those, all of the other nodes are called Covered nodes.
We need to verify whether the sum of all the covered nodes is equal to the sum of all the uncovered nodes.
25
/ \
5 12
/ \ \
2 30 24
/ / \ /
1 19 31 18
Algorithm
We have to go through some finite steps to check the node and to add the sum of the nodes.
Step 1: First we start from the main root node, start going left and we keep going till the left child is present, if absent then we go to the right child and keep going until we reach the leaf node.
Step 2: Now for the right part we keep going right till the right child is present if absent then we go to left child and keep going till we reach the leaf node.
So, from the two steps, we will calculate the sum of all uncovered nodes and then we can subtract and check for equality of the sum of covered and uncovered nodes.
Code in Python
In this code, we have :
- Made a class to easily create nodes for binary tree and kept initial values zero.
- We have calculated the sum of all nodes in the tree by defining a function.
We have calculated the sum of all the uncovered nodes by defining a function.
- We have traversed through each node in InOrder traversal form
- We have passed the data of the above tree to form the tree
We have checked certain conditions and kept conditions for all possible case
- If it is a leaf node
- If it is left than continue left or go right
- If it is right than continue right or go left
# Class to create New node # initially left and right child is None class create_node: def __init__(self, value): self.node = value self.leftchild= self.rightchild = None # Calculating sum of all nodes def Sum(s): if (s == None): return 0 return s.node + Sum(s.leftchild) + Sum(s.rightchild) # Calculate sum # of left border nodes (Recursion) def uncoveredSumLeft(s): # If leaf node, then just return # its nodes value if (s.leftchild == None and s.rightchild == None): return s.node # check for left and then go left # otherwise go right if (s.leftchild != None): return s.node + uncoveredSumLeft(s.leftchild) else: return s.node + uncoveredSumLeft(s.rightchild) # Calculate sum of # right border nodes (Recursion) def uncoveredSumRight(s): # simply return if node is leaf node if (s.leftchild == None and s.rightchild == None): return s.node # check for left and then go right # otherwise go left if (s.rightchild != None): return s.node + uncoveredSumRight(s.right) else: return s.node + uncoveredSumRight(s.left) # Returns sum of all uncovered nodes def uncoverSum(s): # Initializing considering left and right # border to be 0 left_border= 0 right_border = 0 if (s.leftchild != None): left_border = uncoveredSumLeft(s.left) if (s.rightchild != None): right_border = uncoveredSumRight(s.right) # return sum of root node, # left border and right border return s.node + left_border + right_border # Finally checking sum def checksum(root): # Sum of uncovered nodes UnCover_sum = uncoverSum(root) # Sum of all nodes Total_sum = Sum (root) # return True if sum of cover nodes # and uncover nodes is equal return (UnCover_sum == (Total_sum - UnCover_sum )) # Traversing through Inorder traversal def inorder(root): if (root): inorder(root.left) print(root.node, end = " ") inorder(root.right) # Main code if __name__ == '__main__': # Creating the Above diagram # Binary tree # Creating object of above class root = create_node(25) root.left = create_node(5) root.left.left = create_node(2) root.left.right = create_node(30) root.left.right.left = create_node(19) root.left.right.right = create_node(31) root.left.left.left = create_node(1) root.right = create_node(12) root.right.right = create_node(24) root.right.right.left = create_node(18) if (checksum(root)): print("In the given Tree, the Sum of covered and uncovered node is equal") else: print("In the given Tree, the Sum of covered and uncovered node is not equal")
Output
In the given Tree, the Sum of a covered and uncovered node is not equal
[Program finished]
Extra
- We can create more branch of the tree.
- We can calculate the sum of covered and then compare but it will difficult to solve and define.
- We can use other conditions and return True or false (1 or 0)
I hope you understand the theory and the code and find it easy to implement. If you need help or have a doubt please drop a comment. Your feedback to the code and theory will be appreciated.
Leave a Reply