ProgramGuru

Check if a Binary Tree is a Sum Tree

Problem and examples

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.
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.

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

struct Result {
    bool isSumTree;
    int sum;
};

Result checkSumTree(TreeNode* root) {
    if (!root) return {true, 0};
    if (!root->left && !root->right) return {true, root->val};
    Result left = checkSumTree(root->left);
    Result right = checkSumTree(root->right);
    bool isSum = left.isSumTree && right.isSumTree && (root->val == left.sum + right.sum);
    return {isSum, root->val + left.sum + right.sum};
}

int main() {
    TreeNode* root = new TreeNode(26);
    root->left = new TreeNode(10);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(6);
    root->right->right = new TreeNode(3);
    cout << (checkSumTree(root).isSumTree ? "true" : "false") << endl;
    return 0;
}

Python implementation

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

def isSumTree(root):
    if root is None:
        return (True, 0)
    if root.left is None and root.right is None:
        return (True, root.val)
    left_ok, left_sum = isSumTree(root.left)
    right_ok, right_sum = isSumTree(root.right)
    total = left_sum + right_sum
    return (left_ok and right_ok and root.val == total, root.val + total)

if __name__ == '__main__':
    root = TreeNode(26, TreeNode(10, TreeNode(4), TreeNode(6)), TreeNode(3, None, TreeNode(3)))
    print(isSumTree(root)[0])

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class SumTree {
    static class Result {
        boolean isSumTree;
        int sum;
        Result(boolean isSumTree, int sum) {
            this.isSumTree = isSumTree;
            this.sum = sum;
        }
    }

    static Result check(TreeNode root) {
        if (root == null) return new Result(true, 0);
        if (root.left == null && root.right == null) return new Result(true, root.val);
        Result left = check(root.left);
        Result right = check(root.right);
        boolean valid = left.isSumTree && right.isSumTree && (root.val == left.sum + right.sum);
        return new Result(valid, root.val + left.sum + right.sum);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(26);
        root.left = new TreeNode(10);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(3);
        System.out.println(check(root).isSumTree);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isSumTree(root) {
    if (!root) return { isSum: true, sum: 0 };
    if (!root.left && !root.right) return { isSum: true, sum: root.val };
    const left = isSumTree(root.left);
    const right = isSumTree(root.right);
    const total = left.sum + right.sum;
    const isSum = left.isSum && right.isSum && (root.val === total);
    return { isSum: isSum, sum: root.val + total };
}

const root = new TreeNode(26, new TreeNode(10, new TreeNode(4), new TreeNode(6)), new TreeNode(3, null, new TreeNode(3)));
console.log(isSumTree(root).isSum);

Go implementation

package main

import "fmt"

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

type Result struct {
    isSum bool
    sum   int
}

func isSumTree(root *TreeNode) Result {
    if root == nil {
        return Result{true, 0}
    }
    if root.left == nil && root.right == nil {
        return Result{true, root.val}
    }
    left := isSumTree(root.left)
    right := isSumTree(root.right)
    isValid := left.isSum && right.isSum && (root.val == left.sum+right.sum)
    return Result{isValid, root.val + left.sum + right.sum}
}

func main() {
    root := &TreeNode{26, &TreeNode{10, &TreeNode{4, nil, nil}, &TreeNode{6, nil, nil}}, &TreeNode{3, nil, &TreeNode{3, nil, nil}}}
    fmt.Println(isSumTree(root).isSum)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

struct Result {
    is_sum: bool,
    sum: i32,
}

fn is_sum_tree(node: &Option<Box<TreeNode>>) -> Result {
    if let Some(ref n) = node {
        if n.left.is_none() && n.right.is_none() {
            return Result { is_sum: true, sum: n.val };
        }
        let left = is_sum_tree(&n.left);
        let right = is_sum_tree(&n.right);
        let total = left.sum + right.sum;
        Result {
            is_sum: left.is_sum && right.is_sum && n.val == total,
            sum: n.val + total,
        }
    } else {
        Result { is_sum: true, sum: 0 }
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 26,
        left: Some(Box::new(TreeNode {
            val: 10,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
        })),
    }));
    println!("{}", is_sum_tree(&root).is_sum);
}

Kotlin implementation

class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)

data class Result(val isSum: Boolean, val sum: Int)

fun isSumTree(node: TreeNode?): Result {
    if (node == null) return Result(true, 0)
    if (node.left == null && node.right == null) return Result(true, node.value)
    val left = isSumTree(node.left)
    val right = isSumTree(node.right)
    val total = left.sum + right.sum
    return Result(left.isSum && right.isSum && node.value == total, node.value + total)
}

fun main() {
    val root = TreeNode(26,
        TreeNode(10, TreeNode(4), TreeNode(6)),
        TreeNode(3, right = TreeNode(3))
    )
    println(isSumTree(root).isSum)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func isSumTree(_ root: TreeNode?) -> (Bool, Int) {
    guard let node = root else { return (true, 0) }
    if node.left == nil && node.right == nil {
        return (true, node.val)
    }
    let (leftIsSum, leftSum) = isSumTree(node.left)
    let (rightIsSum, rightSum) = isSumTree(node.right)
    let total = leftSum + rightSum
    return (leftIsSum && rightIsSum && node.val == total, node.val + total)
}

let root = TreeNode(26, TreeNode(10, TreeNode(4), TreeNode(6)), TreeNode(3, nil, TreeNode(3)))
print(isSumTree(root).0)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isSumTree(root: TreeNode | null): { isSum: boolean, sum: number } {
    if (!root) return { isSum: true, sum: 0 };
    if (!root.left && !root.right) return { isSum: true, sum: root.val };
    const left = isSumTree(root.left);
    const right = isSumTree(root.right);
    const total = left.sum + right.sum;
    return {
        isSum: left.isSum && right.isSum && root.val === total,
        sum: root.val + total
    };
}

const root = new TreeNode(26, new TreeNode(10, new TreeNode(4), new TreeNode(6)), new TreeNode(3, null, new TreeNode(3)));
console.log(isSumTree(root).isSum);