Overview
Traverse every node in a binary tree: in-order (left-root-right), pre-order (root-left-right), post-order (left-right-root).
Analogy
Reading a book: in-order = left chapter, this chapter, right chapter (alphabetical for BST); pre-order = table of contents first.
Step-by-step
- In-order: traverse(left); visit(root); traverse(right).
- Pre-order: visit(root); traverse(left); traverse(right).
- Post-order: traverse(left); traverse(right); visit(root).
- Level-order (BFS): use a queue.
Visual
1
/ \
2 3
In: 2,1,3 Pre: 1,2,3 Post: 2,3,1
Common mistakes
- Confusing in-order vs pre-order result order.
- Forgetting base case: if node is None: return.
Practice questions
- Print BST values in sorted order (use in-order).
- Serialize and deserialize a tree using pre-order.
Space
O(h) stack, h = tree height
AI Wisdom