Unit 2.4 · about 4 h
99 / 324Tree representation and traversals
Every tree algorithm is a traversal with extra state. The traversal order decides which questions a single pass can answer.
- implement
You can now
- Represent binary trees with node objects and array layouts, and convert between them.
- Implement recursive and iterative preorder, inorder, postorder and level-order traversals with differential tests.
- Diagnose recursion-depth, null-marker and queue-shape defects on skewed, empty and single-node trees.
Covers
- Tree nodes, parent state, recursion and iterative stacks
- Preorder, inorder, postorder and level-order traversal
Study, in this order
3 steps
- Binary tree fundamentalsDSA Handbook - search, trees and heaps
What a binary tree is; Three shape restrictions worth naming; Two ways to store a tree in memory; The post-order recursion template; Recursion depth on skewed inputs
- Tree traversals: pre, in, postDSA Handbook - search, trees and heaps
The five-line skeleton; The canonical tree; Iterative inorder via explicit stack; Iterative pre and post via explicit stack; Building a tree from two of its traversals; Pitfalls that bite
Depth · Skim the LC 297 worked example for the null-marker rule only; the full codec is not implemented here.
- Level-order traversal: BFS on treesDSA Handbook - search, trees and heaps
The trigger; The pattern; What changes between the variants; Two pitfalls that bite
Focus on
- Height convention used here:
height(null) = 0and a leaf has height 1 (nodes on the path). The AVL chapter switches to edges; never mix the two conventions in one argument. - Iterative inorder keeps every ancestor whose left subtree is done but whose value is unemitted; after emitting, move to
cur.right, notNone. - Level order needs the
level_size = len(queue)snapshot taken once per level. Reading the queue length inside the inner loop merges levels. - CPython's default recursion limit is 1000 (check with
sys.getrecursionlimit), so a recursive traversal fails on a skewed tree of a few thousand nodes while a balanced tree of 100,000 nodes (depth about 17) is fine. The iterative forms have no such cap.
Reproduce closed-book
[1,2,4,5,3,6], inorder [4,2,5,1,3,6]), return inorder [4,2,5,1,3,6] and level order [[1],[2,3],[4,5,6]]. Check both against recursive versions on 200 random BSTs up to 25 nodes with fixed seeds, plus empty, single-node and skewed inputs.Traps
- Pushing the left child before the right in iterative preorder. Push right first so the left child pops next.
- Serializing without
nullmarkers. Preorder[2,1]fits two different trees; markers disambiguate. - Using
list.pop(0)as the BFS queue. Each pop costs \(O(n)\), which makes level order \(O(n^2)\); usecollections.deque.
Practice
LeetCode 94: Binary Tree Inorder Traversal
Solve recursively, then iteratively with an explicit stack; the follow-up asks for the iterative form
After submitting, read the AlgoMaster write-up for Binary Tree Inorder Traversal (https://algomaster.io/learn/dsa/binary-tree-inorder-traversal).
LeetCode 102: Binary Tree Level Order Traversal
Group output by level with the snapshot line; example tree [3,9,20,null,null,15,7] expects [[3],[9,20],[15,7]]
After submitting, read the AlgoMaster write-up for Binary Tree Level Order Traversal (https://algomaster.io/learn/dsa/binary-tree-level-order-traversal).
Self-test
-
Why does inorder traversal of a BST emit sorted keys?
Inorder visits the left subtree, then the node, then the right subtree. Every key left of a node is smaller and every key right of it is larger, so induction on the tree gives ascending order. This needs the BST invariant and is false for general binary trees. -
What breaks if the inner level-order loop reads
len(queue)on every check instead of snapshotting?Children appended during the level change the bound mid-level, so the loop consumes the next level too and the boundaries merge. The snapshot fixes the count before any appends happen. -
Preorder
[1,2]and postorder[2,1]fit more than one tree. Show the ambiguity and the fix.Both fit root 1 with a single child 2 on either side; the one-child direction is undetermined. Null markers (or an inorder sequence, which needs distinct keys) fix the shape. -
A recursive inorder fails on a skewed tree of 5,000 nodes but works on a balanced tree of 100,000. Why?
Stack use follows depth, not size: skewed depth is \(n-1 = 4{,}999\) against the default limit of 1000, while balanced depth is about 17. The fix is the iterative form, or a deliberate limit raise.
Completion criterion
Stop when
Both iterative traversals match their recursive twins on 200 random trees, you reproduce the canonical orders from memory, and empty, single-node and skewed inputs all pass.
Mark passed, then open 2.5 Only mark this when you can do it without notes.Leads to
- 2.5 Binary search trees, balance and augmented trees BST operations inherit these traversals and add the ordering invariant.
- 5.6 Tree dynamic programming Post-order aggregation with side state becomes tree dynamic programming.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.