Trees
How Trees work
Before you start
- Open lesson
Recursion
Every tree function here is recursive. That lesson covers base cases and the call stack.
Why it matters
Mirroring trees appears in UI layout, coordinate transforms, and test fixtures for hierarchical data. A production tree may contain millions of nodes, so constructing a second hierarchy doubles object memory and creates avoidable allocation pressure. The mirror must preserve every node and value without allocating a second tree and with extra memory proportional only to the tree's height.
Example
Invert Binary Tree
Invert the binary tree (swap every left/right child) and return the root. Tests use level-order arrays with null omitted at the trailing edge.
- Input
- root = [4, 2, 7, 1, 3, 6, 9]
- Output
- [4, 7, 2, 9, 6, 3, 1]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Invert Binary Tree
root = [4, 2, 7, 1, 3, 6, 9]→[4, 7, 2, 9, 6, 3, 1]
The baseline, Build a mirrored copy, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
For [4, 2, 7, 1, 3, 6, 9], the brute copy allocates seven replacement nodes. Transform the subtrees rooted at 2 and 7, then swap them under 4, reusing every original node.
In [4, 2, 7, 1, 3, 6, 9], nodes 1, 3, 6, and 9 are leaves; calls on their None children return None. At node 2, the returned subtrees rooted at 1 and 3 are ready, so swapping them makes its children 3 and 1.
Node 7 similarly changes from children 6 and 9 to 9 and 6. Once both transformed subtrees return to 4, swap them to produce [4, 7, 2, 9, 6, 3, 1]. Each node waits for its children before changing its links, which is post-order.
Visual anchor
Invert Binary Tree
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.