Check if a Binary Tree is a Sum Tree - Algorithm and Code Examples

Problem Statement❯

Given a binary tree, check whether it is a **Sum Tree**. A Sum Tree is a binary tree in which the value of each non-leaf node is equal to the sum of the values present in its left and right subtrees. Leaf nodes are considered Sum Trees by default. You need to return whether the entire tree satisfies the Sum Tree property.

Examples❯

Input Tree	Is Sum Tree?	Description
[26, 10, 3, 4, 6, null, 3]	true	Every node equals the sum of its left and right children: 26 = 10 + 3, 10 = 4 + 6, etc.
[10, 8, 2, 3, 5]	false	The root node 10 ≠ 8 + 2. Violates the sum tree property.
[0]	true	Single node is trivially a sum tree by definition.
[]	true	An empty tree is considered a valid sum tree (base case).
[20, 8, 12, 3, 5, 6, 6]	false	Some internal nodes do not match the sum of their children: e.g., 12 ≠ 6 + 6.
[44, 9, 13, 4, 5, 6, 7]	true	All internal nodes follow the rule: 9 = 4 + 5, 13 = 6 + 7, 44 = 9 + 13 + (leaf nodes sum).
[18, 8, 10, 3, 5, 6, 4]	false	Although child nodes satisfy sum tree rule, root 18 ≠ 8 + 10, so the whole tree fails.

Solution❯

Case 1: The Tree is Empty

An empty tree (null or None) is trivially considered a Sum Tree because there's nothing to violate the sum condition. So, in this case, the answer is true.

Case 2: The Tree Has a Single Node

If the tree has only one node, it's a leaf. Leaf nodes are always considered Sum Trees by definition, as there are no child nodes to sum. Hence, the answer is true.

Case 3: The Tree Has Internal Nodes and Satisfies the Sum Property

For a non-leaf node, if its value is equal to the sum of values in its left and right subtrees, and both subtrees themselves are Sum Trees, then the entire subtree rooted at this node is a Sum Tree. For example, in the tree:

    26
   /  \
 10    3
/  \     \
4    6     3

Each non-leaf node follows the rule:

4 and 6 are leaves → valid
10 = 4 + 6 → valid
3 is a leaf → valid
26 = 10 + 3 + 3 → valid

So, the output is true.

Case 4: The Tree Has Internal Nodes but Violates the Sum Rule

If any node (other than a leaf) violates the condition — meaning its value doesn't equal the sum of its left and right subtrees — then the tree is not a Sum Tree. For example:

    18
   /  \
  9    8

The root node 18 ≠ 9 + 8 (which is 17), so it fails the check. Therefore, the answer is false.

Case 5: The Tree Contains Mixed Nodes with One Invalid Subtree

Even if most of the tree follows the Sum Tree rule, a single violation anywhere in the tree (in a subtree) makes the entire tree invalid. So, we must recursively validate every node.

Algorithm Steps❯

If the tree is empty, return true with sum = 0.
If the node is a leaf, return true with sum equal to the node's value.
Recursively check the left and right subtrees to obtain their sums and whether they are sum trees.
For the current node, verify that it is a sum tree by checking if its value equals the sum of the left and right subtree sums.
Return true for the current node if both subtrees are sum trees and the node's value equals the left sum plus the right sum; also, return the total sum (node's value + left sum + right sum).
If the condition fails, return false.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSumTree(root):
    # Returns a tuple (isSumTree, sum)
    if root is None:
        return (True, 0)
    if root.left is None and root.right is None:
        return (True, root.val)
    leftIsSum, leftSum = isSumTree(root.left)
    rightIsSum, rightSum = isSumTree(root.right)
    total = leftSum + rightSum
    if leftIsSum and rightIsSum and root.val == total:
        return (True, root.val + total)
    else:
        return (False, 0)

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         26
    #        /  \
    #      10    3
    #     /  \    \
    #    4    6    3
    root = TreeNode(26, TreeNode(10, TreeNode(4), TreeNode(6)), TreeNode(3, None, TreeNode(3)))
    print(isSumTree(root)[0])

⬅ Previous TopicFind Minimum Swaps Required to Convert a Binary Tree into a BST

Next Topic ⮕Check if All Leaf Nodes are at the Same Level in a Binary Tree