Check if a Binary Tree is a SumTree

Problem Return true if a binary tree is a SumTree: every non-leaf node's value equals the SUM of all values in its left and right subtrees. Leaves and empty trees qualify by definition.

Input / Output

• Input: tree root. Output: boolean.

Constraints

• Up to 10^5 nodes; O(n) single traversal — the naive "sum subtree per node" is O(n^2).

Example

• 26(10(4,6), 3(null,3)) → true (10=4+6, 3=0+3, 26=20+6). A node 10(4,5) → false.

Expected approach

• Post-order returning subtree sum with a validity flag (or −1 sentinel / exception on failure): leftSum and rightSum bubble up; non-leaf valid iff node.val == leftSum + rightSum; return node.val + leftSum + rightSum. O(n)/O(h). The trick answer worth mentioning: in a valid SumTree, subtree sum == 2 * child value relationship allows O(1) checks per node under specific definitions — but the robust post-order is what to code. Distinguish from "children-sum property" (direct children only) — a classic conflation probe.