Check if given binary tree is a sum tree or not

Given a binary tree, check if it is a sum tree or not. In a sum tree, value at each non-leaf node is equal to the sum of all elements present in its left and right subtree. The value of a leaf node can be anything.


For example,

Sum Tree



We can easily solve this problem by using recursion. The idea is to traverse the tree in postorder fashion. Then for each non-leaf node, we check if node’s value is equal to sum of all elements present in its left subtree and right subtree. If this relation do not hold true for any node, then the given binary tree cannot be a sum tree.

C++ implementation –

Download   Run Complete Code

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Why do we have to return 2*root->key at the end ? and not just return root->key??


Because root->key is equal to the sum of subtree rooted at root, so the sum of tree rooted at its parent is equal to twice of root->key, as sum is root->key + sum of tree rooted at root which is also root->key by the property of sum tree.


Why are we returning an int here? Is it not boolean as we are checking if it is a sum tree or not?

Also, why are we returning 2*root->key?


INT_MIN here is working as a flag here instead.


Seems the description is misleading here. The node value is “sum of its left and right tree” plus the original value of the node.


Run your code for this input
1(test case)
6(no. of nodes)
0 73 L 0 99 R 73 42 L 73 45 R 99 38 L 99 41 R
The answer should be no but your program is giving answer as yes