Children Sum in a Binary Tree
Every node must equal the sum of its children
A leaf has no children, so it always satisfies the property. For every other node, recurse into both subtrees first, then compare the node's own value against the sum of its children's values — and the whole tree is valid only if every node along the way passes.
Details
Animated on: Given the root of a binary tree, check whether every node with at least one child has a value equal to the sum of its children's values (a missing child counts as 0).
Problem:Children Sum in a Binary TreeMedium
Every node must equal the sum of its children
step 1 / 9
Call checkChildSum(50). Every node with a child must equal the sum of its children's values, and a missing child counts as 0 — so we need an answer from below before 50 can check itself.
1FUNCTION checkChildSum(node):2 IF node has no left AND no right: RETURN true3 leftOk <- true4 rightOk <- true5 IF node.left != null: leftOk <- checkChildSum(node.left)6 IF node.right != null: rightOk <- checkChildSum(node.right)7 sum <- VALUE(node.left) + VALUE(node.right)8 RETURN leftOk AND rightOk AND (node.val = sum)9END FUNCTION
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Call checkChildSum(50). Every node with a child must equal the sum of its children's values, and a missing child counts as 0 — so we need an answer from below before 50 can check itself.
- Node 50 has a child. Its own check has to wait — first recurse down and get an answer for each subtree.
- Node 30 has a child. Its own check has to wait — first recurse down and get an answer for each subtree.
- Node 10 is a leaf — no children to sum, so it trivially satisfies the property and returns true.
- Node 20 is a leaf — no children to sum, so it trivially satisfies the property and returns true.
- Back at 30: its children sum to 10 + 20 = 30, which matches the node's own value 30, so checkChildSum(30) returns true.
- Node 20 is a leaf — no children to sum, so it trivially satisfies the property and returns true.
- Back at 50: its children sum to 30 + 20 = 50, which matches the node's own value 50, so checkChildSum(50) returns true.
- Every node passed its check, so the tree [50, 30, 20, 10, 20] satisfies the children sum property: result = true. Each node was visited exactly once, so this costs O(n) time.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.