DSA Roadmap/Trees

Binary Tree Traversals (DFS & BFS)

The four ways to visit every node in a tree, recursively, iteratively with an explicit stack, and breadth-first with a queue — and why the order you pick changes everything downstream.

!!!2/5Theory: 2h5 problems

Why traversal order is the whole topic

Every tree problem boils down to "visit the nodes in some order and do something at each one." The order you choose is not a stylistic detail — it determines whether the problem is trivial or awkward. Pick preorder when you need to see a node before its children (copying a tree, serializing it); pick postorder when you need to know about a node's children before you can say anything about the node itself (deleting a tree, computing subtree aggregates); pick level-order when the question is fundamentally about depth or "what does the tree look like level by level." Recognizing which order a problem is implicitly asking for is a big part of the pattern-matching skill this topic builds.

There are exactly four traversals worth knowing cold, and they split into two families: three depth-first orders sharing one recursive skeleton, and one breadth-first order built on a queue instead of a stack.

The three DFS orders

OrderSequenceTypical use
Preorderroot → left → rightCopying/serializing a tree (you see a node before deciding where its children go), prefix expression evaluation
Inorderleft → root → rightBinary Search Trees — this is the traversal that yields sorted output (see the BST subtopic)
Postorderleft → right → rootAnything requiring children resolved first: deleting a tree, computing subtree sizes/heights, postfix expression evaluation

All three share one skeleton — only the position of the "visit" line changes:

def traverse(node): if node is None: return # preorder position: visit(node) here traverse(node.left) # inorder position: visit(node) here traverse(node.right) # postorder position: visit(node) here

This is worth memorizing as a single mental template rather than three separate algorithms — you'll reuse this exact skeleton (with a value returned instead of printed) throughout the Advanced Tree Patterns subtopic, and again in Backtracking and DP on Trees later in the roadmap.

Iterative DFS with an explicit stack

Recursion works because the call stack is doing bookkeeping for you implicitly. Interviewers frequently ask for the iterative version specifically to check whether you understand that bookkeeping well enough to do it yourself — this is the single most common follow-up on any traversal question.

Iterative preorder is the easy case, since you can push right before left and pop naturally gives you root-left-right:

def preorder_iterative(root): result, stack = [], [root] if root else [] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result

Iterative inorder is the one that trips people up, because you must go as far left as possible before you're allowed to visit anything:

def inorder_iterative(root): result, stack = [], [] curr = root while curr or stack: while curr: # walk all the way left, remembering the path stack.append(curr) curr = curr.left curr = stack.pop() # backtrack to the deepest unvisited ancestor result.append(curr.val) curr = curr.right # then explore its right subtree return result

Iterative postorder is the hardest to derive from scratch: children must come out before the parent, which is the reverse of what a stack naturally gives you. The standard trick is to compute a modified preorder (root → right → left instead of root → left → right) and reverse the result — that reversal turns "root, right, left" into exactly "left, right, root."

BFS: level-order traversal

Level-order is not "DFS but different" — it's a structurally different algorithm built around a queue instead of a stack, because you want to fully exhaust one depth before touching the next:

from collections import deque def level_order(root): if root is None: return [] result, queue = [], deque([root]) while queue: level = [] for _ in range(len(queue)): # snapshot the current level's size node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

The for _ in range(len(queue)) line is the detail that makes this level-aware rather than just breadth-first: it processes exactly the nodes that were in the queue at the start of the iteration (one full level), before any of their children — enqueued during this pass — get processed. Drop that line and you still get a valid BFS order, but you lose the ability to tell where one level ends and the next begins, which is what most level-order interview questions actually need.

Choosing the right order

If the question is about...Use
Sorted output from a BSTInorder
Copying / rebuilding a tree, or needing the root's value before its subtreesPreorder
Deleting a tree, or computing a value bottom-up (heights, subtree sums)Postorder
Depth, "level N", shortest path in an unweighted tree, or per-row viewsLevel-order (BFS)

Morris traversal — O(1) space (bonus)

All four traversals above use O(h) auxiliary space for the stack or queue. Morris traversal achieves inorder (or preorder) traversal in O(1) extra space by temporarily rewriting None right-pointers to point to the inorder successor, walking the tree using those threads, and then removing them as it backtracks — effectively turning the tree into a temporarily-threaded linked list. It's rarely required to produce from memory in an interview, but knowing it exists — and that it trades a small amount of temporary tree mutation for zero extra memory — is a strong signal of depth if a "can you do this in O(1) space?" follow-up comes up.

Complexity

ApproachTimeSpace
Recursive DFS (any order)O(n)O(h) call stack — O(log n) balanced, O(n) skewed
Iterative DFS (explicit stack)O(n)O(h) — same bound, just explicit instead of implicit
Level-order (BFS)O(n)O(w) — the maximum width of the tree, which is O(n) in the worst case (e.g., a complete tree's last level)
Morris traversalO(n)O(1)

The recursive-space caveat is the one people forget: see the Big-O & Complexity Analysis topic's note on recursion depth — a "free" recursive solution on a skewed (linked-list-shaped) tree of n nodes silently costs O(n) stack space and, in Python specifically, can blow the default recursion limit (~1000) well before n gets large.

Common pitfalls

  • Null root. Every traversal function should handle root is None as its very first check and return the appropriate empty result ([] for a list, not a crash).
  • Single-node tree. A frequent off-by-one source: level-order on one node should produce [[root.val]], not [].
  • Confusing preorder with level-order. Both start at the root, but preorder immediately dives into the left subtree while level-order stays shallow until a level is exhausted — mixing these up is the most common conceptual slip under interview pressure.
  • Using a stack where you need a queue (or vice versa). If you reach for list.pop() on what should be BFS, you'll get depth-first order with the levels scrambled, not a clean error — a subtle bug that's easy to miss on paper.
  • Assuming recursion is always fine. On a sufficiently skewed tree, recursive traversal can be a real correctness risk (stack overflow), not just a performance one — this is exactly why "can you do it iteratively?" is such a standard follow-up.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.