WORLD 3

TREES

Solve a smaller copy: ask each subtree, read level by level, pass down limits, walk a tree of letters.

STAGE 0 Trees tutorial

0:00 / 0:00

The move

Trust each child to answer the same question, then combine their answers at the node. A missing child is the base case. Three lines (base case, recurse left and right, combine) solve most tree problems; a queue reads the tree level by level.

Spot it
The problem says binary tree, root, subtree or BST, or asks for a depth, a height or a path.
Cost
Each node is visited once: O(n) time, and O(h) space for the recursion stack, where h is the height.

16 STAGES Trees problems

☆☆☆☆☆ Clear 5 to finish this world.