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.