Tree Traversal Interview Questions: BFS vs DFS Guide

If you can answer one question in a tree problem, answer this first: do I explore level by level, or do I go deep down one path before backtracking? That single choice, breadth-first search (BFS) versus depth-first search (DFS), determines most tree traversal interview questions. BFS uses a queue and processes nodes by distance from the root. DFS uses recursion or an explicit stack and drives to the bottom before backing up. Everything else, the four DFS orderings, the space tradeoffs, the trick questions about the last level, is a variation on that fork.

This guide covers when to reach for each, the traversal orders you must know cold, the complexity you will be asked to state, and eight problems worth drilling.

The decision: BFS or DFS

Start every tree problem by classifying what the question rewards.

Reach for BFS when the answer depends on levels or distance. Level-order output, "return values by depth," right-side view, minimum depth, and anything phrased as "closest to the root" all map to a queue-based sweep. BFS finds the shallowest solution first, so a shortest-path or minimum-depth question is a strong BFS signal. The classic template pushes the root into a queue, then repeatedly drains one full level while enqueueing children.

Reach for DFS when the answer depends on paths, subtrees, or ancestor relationships. Root-to-leaf paths, subtree sums, "does this path add up to a target," and ancestor comparisons are all natural recursions. DFS lets you carry state down the call stack (the current path, an accumulated sum, the max ancestor seen so far) and combine results as the recursion unwinds. Most tree problems in a coding interview are DFS problems, because most tree problems ask about relationships between a node and its descendants.

A quick mapping using problems from our question bank:

Notice that even the two staff-level problems lean on the same primitives. Difficulty in tree questions comes from what you track during the traversal, not from an exotic traversal.

The four DFS orders (and when order matters)

DFS on a binary tree comes in three depth orderings plus the breadth ordering. You should be able to write all four in under two minutes.

• Preorder (node, left, right): process a node before its children. Use it when a parent's result feeds the children, like serializing a tree or building path prefixes. Binary Tree Paths is naturally preorder: you append the current node, then recurse.
• Inorder (left, node, right): on a binary search tree, inorder visits values in sorted order. This is the single most useful fact about BSTs in interviews. "Validate a BST" and "kth smallest element" both fall out of an inorder walk.
• Postorder (left, right, node): process children before the node. Use it when a node's answer depends on its subtrees. Binary Tree Pruning is textbook postorder: you cannot decide whether to cut a node until you know whether either child survives. Maximum Product of Splitted Binary Tree also needs subtree sums computed bottom-up.
• Level-order (BFS): node by node across each level, left to right.

If an interviewer asks "which traversal?" and you pause, default to reasoning about dependency direction. Parent-informs-child is preorder. Child-informs-parent is postorder. Sorted BST output is inorder.

Recursive vs iterative

Recursion is cleaner and almost always what you should write first. Be ready for the follow-up: "do it iteratively." Preorder and level-order convert to a stack and a queue respectively with little fuss. Iterative inorder is the one people fumble under pressure, because you push left children until you hit null, pop, process, then move right. Practice that specific loop until it is muscle memory, because it is a common "prove you actually understand the stack" prompt. Iterative traversals using an explicit stack are a well-documented pattern worth rehearsing.

Complexity: what to say out loud

State complexity before you are asked. For any traversal that visits every node once, time is O(n). Space is where candidates lose points.

• DFS space is O(h), where h is the tree height, because the recursion (or explicit stack) holds one node per level of the current path. For a balanced tree that is O(log n). For a degenerate, list-like tree it degrades to O(n). Say both.
• BFS space is O(w), where w is the maximum width. For a balanced binary tree the widest level holds about n/2 nodes, so BFS is O(n) in the worst case. This is the tradeoff that trips people up: BFS is not free on memory just because it avoids deep recursion.

If you want to sound sharp, mention Morris traversal, which threads the tree using temporary links to achieve inorder traversal in O(n) time and O(1) extra space, with no stack or recursion. Morris traversal is the O(n) time and O(1) space algorithm for tree traversal. You almost never need to implement it, but naming it signals depth. Do not volunteer to code it unless asked; the pointer bookkeeping is error-prone under a timer.

A worked pattern: Count Complete Tree Nodes

Count Complete Tree Nodes looks like a trivial "traverse and count" until you read the word "complete." A naive DFS is O(n). The intended answer exploits the complete-tree structure: walk the leftmost path and the rightmost path. If their heights match, the subtree is perfect and holds exactly 2^h - 1 nodes, no traversal needed. Otherwise recurse into both children. This runs in O(log^2 n).

That jump from O(n) to O(log^2 n) is exactly the kind of judgment call interviewers reward. The lesson generalizes: read the constraints for structure (complete, balanced, BST, unique values) before you commit to a plain traversal. The structure is usually the whole point of the question.

General trees and graph-shaped trees

Not every tree problem is a binary tree. Several of our harder problems, Sum of Perfect Square Ancestors and Find Minimum Diameter After Merging Two Trees, hand you an undirected tree as an edge list rooted at node 0. Here the mechanics shift slightly:

1. Build an adjacency list from edges.
2. Traverse from the root, and because edges are undirected, skip the node you came from (track the parent) to avoid walking backward.
3. Otherwise it is the same DFS or BFS you already know.

Tree diameter, the longest path between any two nodes, is a canonical multi-tree pattern: run one traversal to find the farthest node, then a second traversal from there, or compute it bottom-up in a single DFS. Interviewers at companies like Google and Meta lean on these graph-shaped tree problems because they test whether you can adapt the primitive rather than pattern-match a memorized template.

How we see candidates fail (and fix it)

Running mock interviews all day, the failure modes are consistent, and none of them are "didn't know BFS."

• Not stating the base case first. Write if not node: return before anything else. Half of tree bugs are missing null checks.
• Choosing the wrong order. Trying to prune or sum subtrees in preorder forces awkward extra parameters. Recognize postorder problems early.
• Silent coding. Tree recursion is invisible unless you narrate what each call returns. Say "this call returns the sum of its subtree" before you write it. If you want to sharpen this, our guide on debugging under pressure covers narrating recursion out loud.
• Forgetting the iterative follow-up. Have the stack-based version ready so the pivot does not rattle you.

Our take: most candidates over-index on memorizing all four traversals and under-practice deciding which one a novel problem needs. Drill the decision, not the syntax.

FAQ

Is BFS or DFS more common in tree interviews?

DFS, by a wide margin. Most tree questions ask about paths, subtree properties, or ancestor relationships, all of which are natural recursions. BFS shows up specifically when the problem mentions levels, depth, or "closest to the root." Learn both, but expect to write DFS more often.

Do I have to write iterative traversals?

Often yes, as a follow-up. Interviewers use "now do it without recursion" to check whether you understand the call stack or just memorized a shape. Practice iterative inorder in particular, since it is the least intuitive of the three.

What is the space complexity of tree traversal?

DFS uses O(h) space for the recursion stack, which is O(log n) for a balanced tree and O(n) for a degenerate one. BFS uses O(w) for the queue, up to O(n) at the widest level. State the worst case explicitly.

When would I actually use Morris traversal?

Almost never in production, but it answers the "can you traverse in O(1) space" stretch question. It threads temporary links back to a node's predecessor to walk inorder without a stack. Name it for credit; only implement it if the interviewer insists.

How should I practice tree problems?

Start with one junior problem per traversal order (Range Sum of BST, Binary Tree Paths, Count Complete Tree Nodes), then move to state-carrying DFS like Maximum Difference Between Node and Ancestor. Do them in a timed mock and narrate every return value aloud.

Sources

• Morris Tree Traversal: The O(N) Time and O(1) Space Algorithm
• Level Order Traversal (BFS) of Binary Tree
• Iterative Preorder, Inorder and Postorder Traversal Using Stack
• Depth-First Search Fundamentals, Hello Interview