Week 39 of 125
TAOCP 2.3.1 Traversing Binary Trees
Sign up or sign in to tick these off and give this week a due date.
-
Binary trees, the three traversal orders (preorder, inorder, postorder), traversal with an explicit stack instead of recursion, and threaded trees where spare null links point to inorder successors.
Time About 8 hours this week
Why it matters
Tree traversal is everywhere: ASTs in your interpreters, DOM trees, file systems. Converting recursion to an explicit stack is a practical skill when recursion depth is a risk.
Before you start
- 2.2.3 Linked Allocation
- Recursion
How to approach it
Implement inorder traversal with an explicit stack and confirm it matches the recursive version on random trees. Then build a threaded tree and walk it without any stack. Compare to the AST visitors from jlox.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Confusing the order in which you push left and right children.
- Threads and real links look identical without the tag bit. Keep the tag.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.