Check for Children Sum Property in a Binary Tree in Python
Children Sum property is that the root’s value must be equal to the sum of the data value of its immediate left child and right child.
We can say that under this property; for every node, the node values must be equal to the sum of its adjacent child which is the left child and right child.
/ \ / \
9 8 7 6
/ \ / \ / \
4 5 6 2 1 5
As you can clearly see in the example that the left child’s and right child’s sum is equal to their source code.
Following are some rules or points which we consider in children sum property.
- We consider value as 0 for a node with a null child.
- If the node is a leaf node, it still satisfies the children sum property as because there is no child of a leaf node.
- If the tree is empty tree than also children sum property is satisfied as we take the left and right child as 0.
Children -sum property can be checked with the help of Binary Tree as well as Queue data structure. Here we are solving it through the Binary Tree.
- We insert each value in the node
- We start to traverse each node in the tree
- While traversing: we check if the value of the nodes is equal to the sum of its left child and right child.
a) If we find the check true than we continue from the first step till the last node or till root! = Null. b) If we find it false we return false.
If we consider the Time and Space Complexity, as we know to traverse each node in a Binary Tree it takes time and space complexity O(n) for completion (execution). Since we are doing it through Binary Tree hence, the time and space complexity will be O(n).
Code in Python to Check for Children Sum Property in a Binary Tree
The direct approach to execute a level order traversal along with a check for each node can be majorly divided into two sections: 1 The conditions, 2 the driver code.
- If the current node has both left and right children and the sum of the left child and right child are equal to the sum of the current node.
- If the current node has just one child either left or right and that left or right child is equal to the current node.
- If the current node is the last(leaf) node.
- In all the above three, the children sum property is maintained(satisfied) or not.
2. The main code where we actually pass the data or the value of the tree to be constructed on which the operations will be performed.
# Class to create a new node # by passing the given value , # left and right pointers kept None (initially) class create_node: def __init__(self, nodevalue): self.value = nodevalue self.left = None #consider no child self.right = None # at beginning # check children sum property # if conditions true, return 1 # check for leaf, both child,and one child def checksum(node): leftchild_value= 0 #initially for left child rightchild_value = 0 #initially for right child # If node is Null or a leaf node # return 1 (true) if(node == None or (node.left == None and node.right == None)): return 1 #condition True else: # If left child is absent then use value # of leftchild_value as left child if(node.left != None): leftchild_value = node.left.value # If right child is absent then use value # of right_value as right child if(node.right != None): rightchild_value = node.right.value # if the node equals sum of its children # return 1(true) else 0(false) if((node.value == leftchild_value + rightchild_value) and checksum(node.left) and checksum(node.right)): return 1 #condition true else: return 0 #condition false # Main code if __name__ == '__main__': #creating node by help of class root = create_node(30) root.left = create_node(17) root.right = create_node(13) root.left.left = create_node(9) root.left.right = create_node(8) root.right.left = create_node(7) root.right.right = create_node(6) root.left.left.left = create_node(4) root.left.left.right = create_node(5) root.left.right.left = create_node(6) root.left.right.right = create_node(2) root.right.right.left = create_node(1) root.right.right.right = create_node(5) if(checksum(root)): print("The created tree satisfies the children sum property ") else: print("The created tree does not satisfy the children sum property ")
The created tree satisfies the children sum property
- Here we have used class so that the implementation or creation of node can be easy.
- As mentioned earlier, we can also implement it with the help of the queue, we will have to append each value as level order traverse can be done with the queue as well.
- We can add more nodes and increase the size of the tree by following the path.
- We can use return true or return false in a place where we have used 1 or 0 respectively.
I hope that the code was understandable and easy to implement. If you have any doubt you can ask and your feedback will be appreciated.