Check children-sum property in a binary tree
Given the root of a binary tree, determine if the binary tree holds children-sum property. For a tree to satisfy the children-sum property, each node’s value should be equal to the sum of values at its left and right node. The value of an empty node is considered as 0.
For example, the following binary tree holds the children-sum property:
The idea is to traverse the binary tree in a postorder fashion. For each non-leaf node, check if the node’s value is equal to the sum of values at its left and right subtree. If this relation does not hold for any node, then the binary tree does not hold children-sum property.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <iostream> #include <climits> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Function to check if a given binary tree holds children-sum property int hasChildrenSumProperty(Node* root) { // base case: empty tree if (root == nullptr) { return 0; } // base case: leaf node if (root->left == nullptr && root->right == nullptr) { return root->data; } int left = hasChildrenSumProperty(root->left); int right = hasChildrenSumProperty(root->right); // if the root's value is equal to the sum of values at its left and right subtree if (left != INT_MIN && right != INT_MIN && root->data == left + right) { return root->data; } return INT_MIN; } int main() { /* Construct the following binary tree 25 / \ / \ / \ 12 13 / \ / \ / \ / \ 7 5 6 7 */ Node* root = new Node(25); root->left = new Node(12); root->right = new Node(13); root->left->left = new Node(7); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); if (hasChildrenSumProperty(root) != INT_MIN) { cout << "Binary tree holds children-sum property"; } else { cout << "Binary tree does not hold children-sum property"; } return 0; } |
Output:
Binary tree holds children-sum property
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// A class to store a binary tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class Main { // Function to check if a given binary tree holds children-sum property public static int hasChildrenSumProperty(Node root) { // base case: empty tree if (root == null) { return 0; } // base case: leaf node if (root.left == null && root.right == null) { return root.data; } int left = hasChildrenSumProperty(root.left); int right = hasChildrenSumProperty(root.right); // if the root's value is equal to the sum of values at its left and // right subtree if (left != Integer.MIN_VALUE && right != Integer.MIN_VALUE && root.data == left + right) { return root.data; } return Integer.MIN_VALUE; } public static void main(String[] args) { /* Construct the following binary tree 25 / \ / \ / \ 12 13 / \ / \ / \ / \ 7 5 6 7 */ Node root = new Node(25); root.left = new Node(12); root.right = new Node(13); root.left.left = new Node(7); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); if (hasChildrenSumProperty(root) != Integer.MIN_VALUE) { System.out.println("Binary tree holds children-sum property"); } else { System.out.println("Binary tree does not hold children-sum property"); } } } |
Output:
Binary tree holds children-sum property
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
# A class to store a binary tree node class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right # Function to check if a given binary tree holds children-sum property def hasChildrenSumProperty(root): # base case: empty tree if root is None: return 0 # base case: leaf node if root.left is None and root.right is None: return root.data left = hasChildrenSumProperty(root.left) right = hasChildrenSumProperty(root.right) # if the root's value is equal to the sum of values at its left and right subtree if left != -float('inf') and right != -float('inf') and root.data == left + right: return root.data return -float('inf') if __name__ == '__main__': ''' Construct the following binary tree 25 / \ / \ / \ 12 13 / \ / \ / \ / \ 7 5 6 7 ''' root = Node(25) root.left = Node(12) root.right = Node(13) root.left.left = Node(7) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) if hasChildrenSumProperty(root) != -float('inf'): print('Binary tree holds children-sum property') else: print('Binary tree does not hold children-sum property') |
Output:
Binary tree holds children-sum property
The time complexity of the above solution is O(n), where n is the total number of nodes. The solution requires O(h) extra space for the call stack, where h is the height of the binary tree.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)