Walking a tree
A list has one obvious visiting order: front to back. A tree does not, so we name the useful orders. For binary trees (each node has at most a left and right child), three recursive orders differ only in when the node itself is handled:
- preorder: node, then left subtree, then right subtree
- inorder: left subtree, then node, then right subtree
- postorder: left subtree, then right subtree, then node
Each has a job. Preorder copies a tree top-down (parents before children). Postorder deletes one safely (children before parents, like deleting a folder's contents before the folder). Inorder is the star of lesson 7-3.
These three all dive deep before backing up, so they are depth-first. The fourth order, level-order, visits ring by ring instead, and you already own the tool for it: the BFS frontier queue from lesson 5-3.
Code exercise · python
Run this. Same six-node tree as the figure, all three depth-first orders. Each function is three lines of real work, and only the position of `out.append` changes.
Code exercise · python
Your turn: implement `level_order(root)` with the BFS pattern from lesson 5-3. Start a deque holding the root, pop from the left, append the popped node's value to `out`, and enqueue its left child then right child (skip Nones). Return `out`.
Quiz
You are deleting a folder tree, and every node must be removed AFTER all its children. Which traversal order?