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

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

  1. If the tree is empty, return true with sum = 0.
  2. If the node is a leaf, return true with sum equal to the node's value.
  3. Recursively check the left and right subtrees to obtain their sums and whether they are sum trees.
  4. 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.
  5. 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).
  6. If the condition fails, return false.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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])