Binary TreesProblem 22 of 35
Check if Binary tree is Sum tree or not
Problem Statement
Given a binary tree, check if it is a Sum Tree. A Sum Tree is a binary tree where the value of every non-leaf node equals the sum of all nodes in its left and right subtrees. Leaf nodes are considered as Sum Trees.
Example:
26
/ \
10 3
/ \ \
4 6 3
Output: true
- Node 10: left(4) + right(6) = 10 ✓
- Node 3: left(0) + right(3) = 3 ✓
- Node 26: left_subtree(4+6+10) + right_subtree(3+3) = 20 + 6 = 26 ✓
Approach 1: Brute Force (Calculate Sum for Each Node)
Intuition
For each non-leaf node, calculate the sum of its left and right subtrees and verify if it equals the node's value. Do this recursively for all nodes.
Algorithm
- If node is null or leaf, return true
- Calculate sum of left subtree
- Calculate sum of right subtree
- Check if node value equals left_sum + right_sum
- Recursively verify left and right children are also sum trees
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int getSum(TreeNode root) {
if (root == null) return 0;
return root.val + getSum(root.left) + getSum(root.right);
}
private boolean isLeaf(TreeNode node) {
return node != null && node.left == null && node.right == null;
}
public boolean isSumTreeBruteForce(TreeNode root) {
// Empty tree or leaf node is sum tree
if (root == null || isLeaf(root)) {
return true;
}
// Get sum of left and right subtrees
int leftSum = getSum(root.left);
int rightSum = getSum(root.right);
// Check current node and recursively check children
if (root.val == leftSum + rightSum &&
isSumTreeBruteForce(root.left) &&
isSumTreeBruteForce(root.right)) {
return true;
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n^2) - For each node, we calculate subtree sum which takes O(n)
- Space Complexity: O(n) - Recursion stack for skewed tree
Approach 2: Optimal (Single Pass - Bottom-Up Verification)
Intuition
In a sum tree, if we know the sum of left and right subtrees, we can verify the current node and also calculate the total sum for the parent. Use bottom-up recursion returning sum, and return -1 if any node violates the sum tree property.
Algorithm
- Return 0 for null nodes
- Return node's value for leaf nodes (they're valid sum trees)
- Get sum from left and right subtrees recursively
- If either returns -1, propagate -1 (invalid)
- Verify: node value should equal left_sum + right_sum
- Return total sum (2 * node.val for non-leaf, as node.val = left + right)
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private boolean isLeaf(TreeNode node) {
return node != null && node.left == null && node.right == null;
}
// Returns sum of subtree if valid sum tree, -1 otherwise
private int checkSumTree(TreeNode root) {
if (root == null) return 0;
// Leaf node: return its value
if (isLeaf(root)) return root.val;
// Get sums from children
int leftSum = checkSumTree(root.left);
int rightSum = checkSumTree(root.right);
// If any subtree is invalid, return -1
if (leftSum == -1 || rightSum == -1) return -1;
// Check if current node satisfies sum tree property
if (root.val != leftSum + rightSum) return -1;
// Return total sum of this subtree
// For non-leaf: total = left + right + node = 2 * node.val
return 2 * root.val;
}
public boolean isSumTree(TreeNode root) {
return checkSumTree(root) != -1;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited exactly once
- Space Complexity: O(h) - Recursion stack depth, where h is height of tree
Key Takeaways
- Sum Tree property: Non-leaf node value = sum of left subtree + sum of right subtree
- Key insight: In sum tree, total subtree sum = 2 * node.val (for non-leaf nodes)
- Bottom-up approach enables single-pass solution
- Return -1 pattern is useful for propagating "invalid" state in tree problems
- Leaf nodes are always valid sum trees (base case)