Study
Binary Tree Interviews: DFS or BFS, Recursion or a Stack?
TrueInterview
October 19, 2026 · 15 min read
Pick the traversal from what the answer is keyed by: a result combined from both subtrees means recursive DFS, one answer per depth means BFS with a frozen level size, and one answer per column means BFS carrying a column index. As of 2026-10-19, TrueInterview's bank holds 126 candidate-reported tree questions from 22 big-tech companies. The most-linked binary tree question, Lowest Common Ancestor of a Binary Tree, appears in 12 candidate write-ups. Its answer combines left and right subtree results, so recursive DFS fits it. Our view: open with recursion, and treat the explicit stack as the follow-up you rehearse for deep or skewed input.
Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.
How do you choose between DFS and BFS in the first minute?
Say out loud what the result is keyed by before you write code. If it is a value combined from the left and right subtrees, write recursive DFS. If it is one value per depth, write BFS that freezes each level. If it is grouped by column, write BFS with a column index. Both traversals visit every node once, so the real trade is space by tree shape.
PracHub's Right Side View guide gives the same instruction in one line: "State the chosen pair before debugging the implementation". The techinterview.org guide to BFS and DFS puts the stakes plainly: "Knowing not just how they work but when to choose each is what separates a passing answer from a strong one".
| What the answer is keyed by | Traversal to write | Reported example | Follow-up to rehearse (our view) |
|---|---|---|---|
| A value combined from both subtrees (ancestor, path sum, validity) | Recursive post-order DFS | Lowest Common Ancestor of a Binary Tree | The same logic on a BST or an N-ary tree |
| One value per depth | BFS that records the level size before popping, as PracHub's guide advises, or right-first DFS that claims each depth once | Binary Tree Right Side View | The left side view, and a sparse-tree test |
| One group per column | BFS carrying a column index | Binary Tree Vertical Order Traversal | Ordering nodes that share a row and a column |
| Sorted order of a BST | In-order DFS, which Wikipedia's article says returns BST keys in ascending order | Validate Binary Search Tree | A bounds-passing DFS instead of in-order |
| Any of the above, on a deep or skewed tree | DFS on an explicit stack; Hello Interview's guide says the call stack reaches O(N) on a skewed tree | Any row above | Keeping the visit order identical after conversion |
The dev.to tutorial on tree traversals says keywords such as closest, minimum depth or level order often hint at BFS.
Our take: keyword matching is the weaker rule. Right Side View contains no level keyword, yet it is a per-depth question; Vertical Order says "order" and still needs column bookkeeping that plain level order lacks. The output key is the rule that survives a reworded prompt, so classify by it and let the keywords confirm.
Which binary tree questions do candidates report, and in which round?
A short list of classic binary tree questions recurs across companies, and most tree questions surface in phone screens. Of the tree questions in the bank, 76 were reported in phone screens, 54 onsite and 11 in online assessments, and one question can appear in more than one round. That makes traversal speed a screening skill first.
The table ranks the binary tree questions by candidate write-up links. The traversal column is our reading of each problem, not a description taken from the reports.
| Question | Write-up links | Filed under (companies) | Natural traversal (our read) |
|---|---|---|---|
| Lowest Common Ancestor of a Binary Tree | 12, of which 6 senior-or-above | Uber, Amazon, ByteDance, Google, Meta, Microsoft | Recursive post-order DFS |
| Binary Tree Right Side View | 8, of which 3 senior-or-above | ByteDance, Amazon, Google, Meta, Microsoft | BFS by frozen level, or right-first DFS |
| Find Path in Fibonacci Tree | 7, all from Databricks write-ups | Databricks | Root-to-node paths, then compare them |
| Binary Tree Vertical Order Traversal | 5, of which 3 senior-or-above | Apple, Amazon, Meta, Uber | BFS with a column index |
| Lowest Common Ancestor (BT / BST / N-ary) | 5, all from Meta write-ups | Meta | DFS over a list of children |
| Binary Tree Maximum Path Sum (with path reconstruction) | 5, of which 1 senior-or-above | Not split here | Post-order DFS that returns a gain and a path |
| Validate Binary Search Tree | 3, all senior-or-above | 3 companies | In-order DFS, or DFS with bounds |
| Serialize and Deserialize Binary Tree | 2, of which 1 senior-or-above | Apple, Amazon, ByteDance, Databricks, DoorDash, Microsoft | Pre-order DFS with null markers |
Write-up links count the candidate write-ups that point to a question; they do not measure how often a company asks it. Our take: do not rank Serialize and Deserialize Binary Tree by its links alone, because it is filed under six companies, as many as Lowest Common Ancestor. Breadth across companies is the better signal of a question you will meet somewhere.
By company, Google and Meta each have 20 tree questions in the bank, Amazon 17, Uber and Snowflake 15 each, ByteDance 14 and Microsoft 11. If your loop is at one of those, the classic rows above are the ones to make automatic. The set is current: 117 of these questions were last reported within the 12 months before 2026-10-19. These are candidate-reported questions reconstructed for practice, not any company's official question list.
How does the rule settle the three most-linked classic questions?
Run the rule on the three most-linked classic questions and each resolves in a sentence. Lowest Common Ancestor is a subtree-combined answer, Right Side View is a per-depth answer, and Vertical Order is a per-column answer. They map to post-order DFS, frozen-level BFS and BFS with a column index, and each has one alternative worth rehearsing.
Lowest Common Ancestor of a Binary Tree: combine two subtree answers
Write-ups from Meta, Microsoft and Amazon candidates link this question, and an Uber phone-screen report was last seen in 2026-09. Each call returns whatever it found in its subtree: p, q, their ancestor or nothing. The first node where both children report a hit is the answer. That is post-order by construction, because a node cannot decide until both children have returned.
The follow-up is the generalisation. Meta candidates reported a Lowest Common Ancestor (BT / BST / N-ary) variant in a phone screen last seen in 2026-08. On a BST you walk down from the root using the ordering and need no recursion at all. On an N-ary tree the two child calls become a loop that counts how many children returned a hit. With parent pointers, the problem turns into finding where two upward paths meet.
Binary Tree Right Side View: one node per depth
Write-ups from Meta and ByteDance candidates link it, and a ByteDance phone-screen report dates from 2026-05. PracHub's guide says to record the level size "before removing anything, then pop exactly that many nodes". The last node popped at each level is the visible one. The DFS alternative visits right before left and records a depth only the first time it reaches it. PracHub's guide warns that overwriting the answer at every encounter lets later left-subtree nodes replace the rightmost ones.
Two misreadings fail here. PracHub's guide shows that following right pointers from the root gives an incomplete view on a sparse tree, and notes that the task is not choosing the numerically largest value per level.
Our take: write BFS first for Right Side View. The level boundary is explicit in the code, which makes the correctness argument easy to say aloud. Keep right-first DFS ready for the moment the interviewer asks for space proportional to height instead of width.
Binary Tree Vertical Order Traversal: group by column
Write-ups from Meta, Apple and Amazon candidates link it, and an Apple phone-screen report dates from 2026-07. Carry a column index with each node: the root sits in column zero, a left child one column to the left, a right child one column to the right. BFS is the right pick because it emits nodes top to bottom, so the order inside each column is already correct. A DFS needs the row as well and a sort at the end. Track the smallest and largest column as you go and you can skip sorting the column keys.
Should you write recursion or an explicit stack?
Write recursion first. Hello Interview's DFS guide says DFS is typically implemented as a recursive function. In our view, the recursive version is also shorter and easier to argue about under time pressure. Switch to an explicit stack when the tree can be deep and skewed, or when the interviewer asks for the iterative version.
The cost of recursion is the height of the tree. Hello Interview's guide explains that "the call stack only holds the frames along the current path from the root down to the node being visited, so its depth is the height of the tree". The techinterview.org guide puts that depth at O(V) for a linear chain and O(log V) for a balanced tree. The same guide says recursive DFS hits Python's recursion limit at about 1000 levels and recommends an explicit stack for large inputs.
When you convert, keep the visit order. PracHub's guide says, "To visit the right child first, push the left child first and then the right child". Its guide also warns that pushing the right child first reverses the intended pop order. Carry the selection rule across unchanged: if the recursive version claims each depth once, the stack version must too.
| Criterion | Recursive DFS | Explicit-stack DFS | BFS with a queue |
|---|---|---|---|
| Extra space | O(h), the current root-to-node path (Hello Interview's guide) | O(h), held in your own stack | O(width), the widest level (dev.to tutorial) |
| Balanced tree | O(log N) | O(log N) | Up to about half the nodes, in the last level |
| Skewed tree | O(N) call frames | O(N) entries, with no recursion limit | One node per level |
| Typical failure | Python's limit near 1000 frames, per techinterview.org's guide | Wrong push order reverses the visit order | An unfrozen level merges depths |
| Best for | Your opening answer on almost every tree question | Deep or skewed input and the iterative follow-up | Per-depth and per-column output |
Our take: no evidence we found says interviewers require the explicit-stack version up front, so do not open with it. State the height-based cost in one sentence after the recursive solution, and offer the iterative version if the input could be shaped like a linked list. In our view, stating that trade before being asked turns the follow-up into a short conversation rather than a rewrite.
Which traversal order fits which problem?
Match the order to what each node needs to know when you visit it. Pre-order acts before the children, in-order between them, post-order after them, and level order by depth. Wikipedia's tree traversal article lists the classic uses: pre-order to copy a tree and post-order to delete one.
The same Wikipedia article says pre-order or post-order paired with in-order describes a tree with distinct elements uniquely. Serialize and Deserialize Binary Tree avoids that distinct-element condition by writing null markers into a single pre-order pass.
| Order | What a node knows when you visit it | Reported question that needs it |
|---|---|---|
| Pre-order | State passed down from its ancestors | Serialize and Deserialize Binary Tree |
| In-order | Every smaller key in a BST has been seen | Validate Binary Search Tree, Convert BST to Sorted Doubly Linked List (LC 426), linked from a staff-plus or manager write-up |
| Post-order | Both children's results | Binary Tree Maximum Path Sum (with path reconstruction) |
| Level order | Its depth | Binary Tree Right Side View |
The dev.to tutorial's interview tip is to write all three DFS traversals from memory.
Our take: memorising the templates is the floor, and it is overrated as a target. The reported set rewards knowing which order a problem needs and why, and that comes from solving the recurring questions above, each in its natural order plus one alternative.
Where do correct-looking traversals fail?
A traversal can visit every node and still return the wrong answer when the bug is in ordering rather than in the choice of algorithm. Check where a BFS level ends, which child goes on the stack first, and whether an answer is written once or overwritten.
PracHub's guide describes the first trap exactly: "Draining the live queue while appending children can silently combine several depths into one batch, even when every node is visited". The same guide says sparse examples reveal errors that a perfect tree with all children present can hide.
| Bug | What goes wrong | Where it is described |
|---|---|---|
| Unfrozen BFS level | Several depths land in one batch | PracHub's guide |
| Right child pushed first | The stack pops in reverse of the intended order | PracHub's guide |
| Answer overwritten per visit | Later left-subtree nodes replace the rightmost ones | PracHub's guide |
| Missing base case | Recursion runs past the leaves | The dev.to tutorial lists it as a common mistake |
| Python list used as a queue | Each pop from the front moves the remaining items | PracHub's guide |
| Tree modified mid-traversal | Later visits see changed links | The dev.to tutorial lists it as a common mistake |
Our take: before you say "done", trace one sparse, left-heavy tree with a single deep left branch. It exposes the unfrozen level, the push-order mistake and the overwritten answer in one pass, which a balanced example will not.
How does the tree question stretch from phone screen to onsite?
Onsite tree questions carry graph and backtracking tags more often than phone-screen ones. Graph tags sit on 14 of the 76 phone-screen tree questions and on 18 of the 54 onsite ones, and backtracking tags rise from 9 to 14. Our view: a screen mainly checks that your traversal is fast, while the onsite tag mix points to more graph-style work.
Across all 126, graphs tags appear on 25 and backtracking on 18. Google and Meta each carry graph tags on 7 of their 20 tree questions, Amazon on 6 of 17 and Uber on 6 of 15. The tags do not say what those questions ask. In our reading, graph-style reasoning on a tree usually means walking to parents, starting a search from an arbitrary node, or enumerating paths, and each breaks the assumption that the root is where you begin.
Recent non-classic variants that move away from the left-right binary template:
| Company | Question | Round | Last reported |
|---|---|---|---|
| Merge N-ary Trees by Node Key | Onsite | 2026-08 | |
| Databricks | Find Path in Fibonacci Tree | Phone screen | 2026-07 |
| Snowflake | Tree Height After Node Removal | Phone screen | 2026-07 |
Our take: get the classic set fast for screens, then spend the week before an onsite on tree questions that also need graph-style traversal. An N-ary variant removes the left-right symmetry you lean on, and a path question forces each call to return more than a number. Both expose a traversal you only half own.
What changes at senior and staff level?
The level data shows no separate senior tree set. Write-up links to these questions come 98 times from candidates who reported a senior, staff-plus or manager level and 119 times from junior, new-grad or intern candidates. Lowest Common Ancestor of a Binary Tree splits evenly, 6 and 6.
Levels here are self-reported on each write-up. Binary Tree Right Side View draws 3 senior-or-above links, one of them staff-plus or manager, against 5 junior-or-below. By algorithm topic, backtracking is the one that leans senior, at 32 senior-or-above links to 29 junior-or-below. The lean is slight, so read it as a hint rather than a rule: in our reading, backtracking on a tree is usually path enumeration, which makes one path-enumeration variant worth rehearsing.
Our take: at senior level the question is usually the same, so the bar shows in the reasoning around it. Justify the traversal from the output key, state space by tree shape without being asked, and handle the iterative or N-ary follow-up without restarting your solution. A staff candidate who needs a hint to see that Right Side View is a per-depth question has lost more than a junior who does.
Down-leveling note (our view): treat traversal fluency as protection rather than proof, because a stalled follow-up in a tree screen can end the loop before the later rounds you are counting on to show your level.
How we counted
Counts come from TrueInterview's question bank as of 2026-10-19 and cover 126 tree practice questions candidates reported at 22 big-tech companies. A question can be filed under several companies and reported in several rounds, so tallies overlap. Level splits use the level each candidate reported, and a link count measures what candidates wrote up, not how often a company asks a question. Some tree-tagged titles, such as design or leaderboard problems, do not read as binary tree questions, so the tables leave them out.
FAQ
Is DFS or BFS easier to write under time pressure?
Recursive DFS usually is. It needs a base case and two calls, with no queue and no level bookkeeping. Hello Interview's guide defines the base case as the condition that stops DFS from traversing further down. BFS earns its extra lines when the output is indexed by depth or column, because the level boundary in the loop is then the logic the problem asks for. If you are unsure which a problem needs, write the recursive version first and convert only when the output key demands it.
Do BFS and DFS differ in time complexity on a tree?
No. The techinterview.org guide puts both at O(V + E) time. On a tree, each visits every node once. The difference is space. The dev.to tutorial says DFS uses space proportional to the tree height. The dev.to tutorial adds that deep, narrow trees favor DFS while shallow, wide trees favor BFS. State that trade by tree shape when you give your complexity, rather than calling one traversal faster.
When should you use BFS instead of DFS on a binary tree?
Use BFS when the answer is indexed by depth or by column, or when you want the shallowest node that meets a condition. The techinterview.org guide notes that each BFS level corresponds to one tree level. That is why Right Side View, level-order output and minimum depth fit BFS naturally: the level boundary already sits in the loop, and minimum depth can stop at the first leaf it meets instead of exploring the whole tree.
Will the interviewer expect an iterative, explicit-stack version?
Treat it as a follow-up to be ready for, as the recursion section argues. Rehearse the conversion on Binary Tree Right Side View, because its right-first DFS makes order mistakes visible: run the recursive and stack versions on the same sparse, left-heavy tree and check that both return the same node at every depth. If they differ, the push order or the claim-once rule changed during the rewrite.
Your practice plan
A three-week plan for someone working full time:
- First week, early. Solve Lowest Common Ancestor of a Binary Tree with recursive DFS, then rewrite it on an explicit stack. Say the output key aloud before each attempt.
- First week, late. Solve Validate Binary Search Tree twice: once with in-order DFS and once by passing bounds down.
- Second week, early. Solve Binary Tree Right Side View with frozen-level BFS, then with right-first DFS that claims each depth once. Test both on a sparse, left-heavy tree.
- Second week, late. Solve Binary Tree Vertical Order Traversal with BFS and a column index, tracking the column range as you go.
- Third week, early. Solve Serialize and Deserialize Binary Tree and Binary Tree Maximum Path Sum (with path reconstruction), returning the path as well as the value.
- Third week, late. Before an onsite, take one N-ary or path variant: Merge N-ary Trees by Node Key or Lowest Common Ancestor (BT / BST / N-ary).
- Throughout. Run each solution against hidden tests; TrueInterview says its coding answers are judged on hidden tests that show the case you failed. When a test fails, check the level boundary and push order first.
Sources
- TrueInterview question bank — tree at big-tech companies — counted 2026-10-19
- Binary Tree Right Side View: BFS Levels, Right-First DFS, and Sparse Trees | PracHub Knowledge Hub — checked 2026-10-19
- BFS vs DFS: When to Use Each with Examples – techinterview — checked 2026-10-19
- Tree traversal - Wikipedia — checked 2026-10-19
- Fundamentals | Hello Interview — checked 2026-10-19
- Tree Traversals Explained: DFS, BFS, and When to Use Each - DEV Community — checked 2026-10-19
- Interview prep compared: your application, end to end · TrueInterview — checked 2026-10-19
Last reviewed: 2026-10-19.