Check if a Binary Tree is a Sum Tree - Visualization

Binary Trees

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❯

Understanding the Problem

A Sum Tree is a special type of binary tree where each non-leaf node's value is equal to the sum of the values of its left and right subtrees. Leaf nodes are considered valid by default. The goal is to check whether the given binary tree satisfies this property throughout all of its nodes.

We will solve this step by step using an example, and understand how to recursively validate the sum tree condition for each node, making it beginner-friendly with intuitive logic.

Step-by-Step Solution with Example

Step 1: Consider a sample binary tree

        26
       /       10    3
    /          4    6     3

We need to check whether this entire tree is a Sum Tree. We will do this recursively, starting from the bottom-most nodes and moving upward.

Step 2: Check leaf nodes

In this tree, nodes 4, 6, and the right 3 are all leaf nodes. Since leaf nodes are always considered valid Sum Trees (they have no children to compare with), we mark them as valid.

Step 3: Check node with value 10

Now move up to the node 10. Its left and right children are 4 and 6 respectively. Since both are leaves and valid, and 10 = 4 + 6, node 10 satisfies the Sum Tree condition.

Step 4: Check node with value 3 (right child of root)

This node only has a right child: another 3, which is a leaf. Since this node doesn’t have a left child, we treat its left sum as 0. So 3 = 0 + 3, which is valid.

Step 5: Check root node 26

The left subtree rooted at 10 sums to 10, and the right subtree rooted at 3 sums to 6 (3 + 3). So, we compute total child sum = 10 + 6 = 16. But wait — that’s incorrect. Actually, the right subtree has value 3 (node) + 3 (leaf) = 6, but the subtree rooted at 10 includes 4 and 6, so total left sum = 4 + 6 + 10 = 20, which is not allowed. That’s not how Sum Tree validation works.

Correction: When validating as a Sum Tree, we should not include the parent node’s value. Instead, we only use child subtree sums. So:

  • Left subtree (10): total sum = 4 + 6 = 10
  • Right subtree (3): total sum = 3 (right leaf only)
  • So total = 10 + 3 = 13, but root is 26

This seems inconsistent. Let's re-define how we compute the subtree sums to include all children correctly. Actually, the definition is: a node’s value must be equal to the sum of values in its left and right subtrees (including all their nodes, not just their direct children). To handle this precisely, we need to return both whether the subtree is a Sum Tree and what its total sum is.

So for the given tree:

  • 4 and 6 → leaves → sum = 4 and 6
  • 10 = 4 + 6 → valid → sum = 10
  • Leaf 3 → sum = 3
  • Right 3 (with child 3) → sum = 6 → 3 = 3 (valid) → sum = 6
  • Now check root 26 → left subtree sum = 10, right subtree sum = 6 → 10 + 6 = 16 ≠ 26 ❌

So the tree fails the Sum Tree condition at the root. The correct tree should be:

        26
       /       10    16
    /     /     4    6 7    9

Now it satisfies: 10 = 4 + 6, 16 = 7 + 9, 26 = 10 + 16 ✅

Edge Cases

Case 1: Empty Tree

An empty tree is trivially considered a Sum Tree. There are no nodes to violate the rule. So the result is true.

Case 2: Single Node Tree

A tree with a single node (a leaf) is always a valid Sum Tree because there are no children to compare. So, it's true.

Case 3: Violation at Any Node

Even if one node (that’s not a leaf) fails the condition node.val ≠ leftSum + rightSum, the whole tree is invalid as a Sum Tree. The check must be applied recursively across the entire structure.

Case 4: Subtree Satisfies, But Root Violates

If all the child subtrees are valid but the root itself violates the rule, then the tree is still not a Sum Tree. Every node must obey the property — including the root.

Finally

To determine if a binary tree is a Sum Tree:

  • Use post-order traversal (left-right-root).
  • At each node, get the sum of left and right subtrees and verify the condition.
  • Return both the validity and total sum from each subtree check.

This approach ensures we check all nodes while efficiently calculating and validating the required sum property. Edge cases like empty trees and single nodes are handled by default in the recursive logic.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

typedef struct Result {
    int isSumTree;
    int sum;
} Result;

Result checkSumTree(TreeNode* root) {
    Result res;
    if (root == NULL) {
        res.isSumTree = 1;
        res.sum = 0;
        return res;
    }
    if (root->left == NULL && root->right == NULL) {
        res.isSumTree = 1;
        res.sum = root->val;
        return res;
    }
    Result left = checkSumTree(root->left);
    Result right = checkSumTree(root->right);
    int total = left.sum + right.sum;
    res.isSumTree = left.isSumTree && right.isSumTree && (root->val == total);
    res.sum = root->val + total;
    return res;
}

int main() {
    TreeNode* root = createNode(26);
    root->left = createNode(10);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(6);
    root->right->right = createNode(3);
    Result res = checkSumTree(root);
    printf("%s\n", res.isSumTree ? "true" : "false");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...