Python | Check sum of Covered and Uncovered nodes of Binary Tree

By Taanvi Goyal

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

  1. If it is a leaf node
  2. If it is left than continue left or go right
  3. 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

  1. We can create more branch of the tree.
  2. We can calculate the sum of covered and then compare but it will difficult to solve and define.
  3. 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