Depth-First Tree Traversal

Foundations

A binary tree stores values in linked node objects, TreeNodes. Each node holds a value, val, and two pointers to its children, left and right, with None for a missing one. The top node is the root, nodes without children are leaves, and a node's depth counts the links down from the root, so the root sits at depth 0. A node together with everything below it is a subtree, itself a binary tree.

Inputs usually list a tree in level order: the root, then each level left to right, with None for a missing child. Reading nums = [7, 1, 5, 3, 6] that way builds five linked nodes: 7's left points to 1 and its right to 5, and 1 points to 3 and 6. In memory there is no list, only separate node objects, each reached through its parent's pointer.

A depth-first traversal handles a whole tree with one recursive function, visit(node): if node is None, return; otherwise call visit(node.left), then visit(node.right), then do the node's own work. Doing that work after both calls is called post-order. On the tree from nums, 3 and 6 finish first, then 1, then 5, and the root, 7, finishes last. Each node is visited once, and the call stack holds one frame per level.

• Recursion

  Every tree function here is recursive. That lesson covers base cases and the call stack.

  Open lesson

Case Scenario

Invert Binary Tree asks for the mirror image: every node's left and right children trade places, all the way down. Post-order fits, because a node can swap its children once each child's subtree is already mirrored. For root = [4, 2, 7, 1, 3, 6, 9], the answer is [4, 7, 2, 9, 6, 3, 1].

The quick fix builds a mirrored copy: a new node for every node, with its subtrees created in swapped order. It is O(n) time, but it allocates a second tree of n nodes, so a tree of millions of nodes briefly needs twice the memory. Nothing in the question needs a copy: every node can be reused with its two links exchanged.