Sum Tree

Medium
1968.

Sum Tree

Sum Tree is a medium coding problem on depth-first search, trees and recursion, asked in Amazon interviews.

Given the root of a binary tree, decide whether it is a sum tree: for every node that is not a leaf, the node's value equals the sum of all the values in its left subtree plus the sum of all the values in its right subtree.

An empty subtree sums to 0, and a leaf is a sum tree on its own. Return true if the whole tree is a sum tree, otherwise false.

Example 1

Input
root = [26,10,3,4,6,null,3]
Output
true
Explanation
10 = 4 + 6, 3 = 3, and 26 = (10 + 4 + 6) + (3 + 3).

Example 2

Input
root = [3,1,2]
Output
true
Explanation
3 = 1 + 2, and leaves need nothing.

Example 3

Input
root = [10,20,30,10,10]
Output
false
Explanation
20 = 10 + 10, but the root's subtrees add up to 40 + 30 = 70, not 10.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSumTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum Tree — Solution in Python, Java & C++

Sum Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Sum Tree is a medium coding problem on depth-first search, trees and recursion, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees, Recursion
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, decide whether it is a sum tree: for every node that is not a leaf, the node's value equals the sum of all the values in its left subtree plus the sum of all the values in its right subtree.

An empty subtree sums to 0, and a leaf is a sum tree on its own. Return true if the whole tree is a sum tree, otherwise false.

Example 1

Input: root = [26,10,3,4,6,null,3]
Output: true
Explanation: 10 = 4 + 6, 3 = 3, and 26 = (10 + 4 + 6) + (3 + 3).

Example 2

Input: root = [3,1,2]
Output: true
Explanation: 3 = 1 + 2, and leaves need nothing.

Example 3

Input: root = [10,20,30,10,10]
Output: false
Explanation: 20 = 10 + 10, but the root's subtrees add up to 40 + 30 = 70, not 10.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 10^5

Hints for Sum Tree

  1. Hint 1

    Checking each node against freshly computed subtree sums repeats work — O(n²) on a chain.

  2. Hint 2

    Have one post-order function return the sum of a subtree, so a parent gets both children's sums in O(1).

  3. Hint 3

    In a valid sum tree, a non-leaf subtree's total is exactly twice its root's value. Return a sentinel like -1 as soon as any node fails, and propagate it.

How to solve Sum Tree

A post-order traversal computes subtree sums bottom-up and checks each internal node against its children's sums in the same pass, returning a sentinel once anything fails.

Approach

  1. Define check(node): for an empty tree return 0; for a leaf return its value.
  2. Otherwise compute l = check(left) and r = check(right); if either is -1 or node.val != l + r, return -1.
  3. Else return node.val + l + r (which equals 2 · node.val).
  4. The tree is a sum tree when check(root) is not -1.

Why it works

By induction check returns the true sum of any subtree that is itself a sum tree, and -1 otherwise (all values are positive, so -1 is never a real sum). A node is then valid exactly when its value equals the two returned sums, which is the definition.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Comparing a node with its children's values only is wrong — the definition uses whole-subtree sums.
  • Leaves are always fine, and a node with one child compares against that child's subtree sum plus 0.

Reference solution

Python

from typing import Optional

def isSumTree(root: Optional[TreeNode]) -> bool:
    return _check(root) != -1

def _check(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return node.val
    l = _check(node.left)
    if l == -1:
        return -1
    r = _check(node.right)
    if r == -1 or node.val != l + r:
        return -1
    return node.val + l + r

Java

public static boolean isSumTree(TreeNode root) {
    return sumCheck(root) != -1;
}

static int sumCheck(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null && node.right == null) return node.val;
    int l = sumCheck(node.left);
    if (l == -1) return -1;
    int r = sumCheck(node.right);
    if (r == -1 || node.val != l + r) return -1;
    return node.val + l + r;
}

C++

static long long sumCheck(TreeNode* node);

bool isSumTree(TreeNode* root) {
    return sumCheck(root) != -1;
}

static long long sumCheck(TreeNode* node) {
    if (!node) return 0;
    if (!node->left && !node->right) return node->val;
    long long l = sumCheck(node->left);
    if (l == -1) return -1;
    long long r = sumCheck(node->right);
    if (r == -1 || node->val != l + r) return -1;
    return node->val + l + r;
}

JavaScript

var isSumTree = function(root) {
    return sumCheck(root) !== -1;
};

function sumCheck(node) {
    if (node === null) return 0;
    if (node.left === null && node.right === null) return node.val;
    var l = sumCheck(node.left);
    if (l === -1) return -1;
    var r = sumCheck(node.right);
    if (r === -1 || node.val !== l + r) return -1;
    return node.val + l + r;
}

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals