Tree Traversals

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A traversal visits every node once. DFS (pre / in / post) goes deep with a stack; BFS (level order) goes level by level with a queue.

   #1
2. ↯use it when

   Levels, rows, "nearest" → BFS. Sorted BST order → inorder. Copy / serialize → preorder. Children before parent → postorder.

   #2
3. { }template

   BFS: offer(root); while (!q.isEmpty()) { int size = q.size(); for (i < size) { poll; offer kids; } }

   #3
4. { }template

   Iterative inorder: while (cur != null || !st.isEmpty()) { while (cur != null) { push; cur = cur.left; } cur = pop(); visit; cur = cur.right; }

   #4
5. O( )cost

   All traversals O(n) time. DFS space O(h): 20 frames for a balanced 10⁶-node tree, 10⁶ for a chain. BFS space O(w): up to n/2.

   #5
6. !trap

   for (int i = 0; i < queue.size(); i++) mixes levels — the queue grows inside the loop. Freeze size first.

   #6
7. !trap

   ArrayDeque rejects null: check children before offer. Need nulls in the queue (serialization)? Use LinkedList.

   #7
8. ✦pro tip

   Distance can go up too? Store parents in a HashMap, then BFS with a seen set — the tree is now an undirected graph.

   #8
9. ✦pro tip

   Serialize = preorder + # for every null + a separator. One traversal with markers rebuilds the exact tree.

   #9

Shaky on a card? Open the chapter or flip its recall cards.