Tree Traversal Interview Questions
Trees are the friendly face of graphs. Interviewers love them because they start tidy—left and right children, predictable base cases—then quietly add a back edge, a parent reference, or a "serialize this shape" constraint and watch how you adapt. Strong candidates code both recursive and iterative versions when time allows, because production debugging often happens in a stack trace, not in elegant three-line recursion.
Traversal choices that matter
- BFS (level-order): shortest path on unweighted trees, level-wise aggregation, zigzag variants. Mention queue space and what you would do for a tree millions of nodes wide (often you cannot materialize every child pointer at once).
- DFS inorder/preorder/postorder: BST order properties, expression trees, subtree sums—know which order preserves the invariant you need.
- Graph mode: visited sets, cycle detection, coloring—when the prompt sneaks in an undirected edge or a directed dependency graph.
Talking through edge cases
Empty tree, single node, skewed tree (linked-list shaped), deep recursion limits in your language—say them early. If you mutate the tree, say so; if you need to return a new structure, clarify whether sharing subtrees is allowed. Those thirty seconds save painful rewrites.
Real-world hooks
Org charts, folder structures, ASTs, feature flag inheritance—pick one you have touched. Relate traversal order to a bug you chased: wrong aggregation at a parent, missing clone on mutation, infinite loop when a reference cycle appeared. Then jump to dynamic programming when problems ask for optimal subtree scores; many tree DP solutions are just DFS with a return value that carries accumulated cost.
Trees in Azure-shaped products
BFS to collect dependency depth (resource groups → nested templates)
// TypeScript: fake adjacency list for ARM/Bicep resource graph
function maxDepth(graph: Record<string, string[]>, root: string): number {
const q: [string, number][] = [[root, 1]];
let best = 0;
while (q.length) {
const [id, d] = q.shift()!;
best = Math.max(best, d);
for (const child of graph[id] ?? []) q.push([child, d + 1]);
}
return best;
}Infrastructure templates nest: Key Vault references, private endpoints, subnets. Debugging "who blocks delete?" is a graph walk, often BFS for shortest dependency chain. Same skill as tree interviews—only the nodes are uglier strings.
Questions with sample answers
These are interview-ready outlines—sound human by swapping in your own metrics, team names, and war stories. The examples are generic on purpose so you can map them to what you actually shipped.
Primary prompt
Serialize and deserialize a binary tree—discuss delimiter choices and robustness to malformed input.
Preorder with null markers:
1,2,null,null,3,4,null,null,null. Use delimiter that cannot appear in values (comma + null token) or length-prefix. Deserialize with index or queue; validate extra tokens = malformed.Primary prompt
Lowest common ancestor in a BST vs arbitrary binary tree with parent pointers—compare approaches.
BST: walk from root: if both < node go left; both > go right; else node is LCA—O(h). With parent pointers: lift depth to same level, then ascend together until meet—O(h). Binary tree without parent: single DFS from root returning (foundA, foundB, lca)—O(n).
Primary prompt
Zigzag level order traversal—how do you keep space reasonable for wide trees?
BFS level-by-level: two deques or reverse alternate levels; space O(w) where w = max width. For extremely wide levels, that's inherent—you must hold the frontier.
Primary prompt
Diameter of a binary tree—how does a single DFS pass carry the answer upward?
For each node, longest path through it = left height + right height; global max is diameter. DFS returns height; O(n) one pass.
Example: skewed tree diameter = n-1; balanced tree often passes through root.
Follow-ups interviewers often ask
Expect nested "why?" questions—brief answers here; expand with your production defaults.
Follow-up
Iterative vs recursive: when do you choose each in production code?
Recursive for clarity when depth bounded; iterative with explicit stack when deep trees risk stack overflow or in languages with tight stack limits.
Follow-up
What if the tree is extremely deep—stack overflow risks and mitigations?
Morris traversal O(1) space (threads), or iterative stack, or increase stack size / tail-call languages—honestly prefer iterative for unknown depth.
Follow-up
How do you test tree questions without giant fixtures?
Single node, two nodes, skewed left/right, full tree height 3, empty null—round-trip serialize/deserialize property tests.
Follow-up
When does the problem become a graph—what extra state do you need?
Back edges or multiple parents → visited set + explicit cycle handling; BFS/DFS from each component; distinguish directed vs undirected.
Follow-up
How would you parallelize subtree computations (conceptual trade-offs)?
Independent subtrees can compute heights in parallel; synchronization cost often dominates small trees; map-reduce over forest for very large static trees offline.