Pattern visualizer

Children Sum Property

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. 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)..

Every node must equal the sum of its children

time O(n)space O(h) recursion stackstep 1 / 9

line 1

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.

Pseudocode

1FUNCTION checkChildSum(node):
2  IF node has no left AND no right:  RETURN true
3  leftOk <- true
4  rightOk <- true
5  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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap