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.
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 –
// Data structure to store a Binary Tree node
Node *left, *right;
// Recursive function to check if given binary tree is a sum tree or not
int isSumTree(Node *root)
// base case: empty tree
if (root == nullptr)
// special case: leaf node
if (root->left == nullptr && root->right == nullptr)
// if root's value is equal to sum of all elements present in its
// left and right subtree
if (root->key == isSumTree(root->left) + isSumTree(root->right))
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.
Thanks for reading.