Binary Trees Coding Interview: Derive, Don't Recite

A binary trees coding interview question is not a memory test. It is a reasoning test with a picture attached. The interviewer wants to watch you name the shape of the data, decide what must be true at every node, choose a traversal order deliberately, and trace the recursion on a sketch. If you can do those four things, you can derive most tree questions live, even ones you have never seen.

This guide walks through that reasoning habit step by step, with worked examples, a recovery script for when an answer goes wrong mid-sentence, and a practice routine you can run out loud.

Why Binary Trees Coding Interview Questions Show Up

Trees test something the array and string questions cannot. Arrays are index-based and mostly iterative. Trees are recursive by nature, and recursion is where many otherwise capable candidates freeze. If you have practised iterative, index-based reasoning in our sorting coding interview guide, you already have half the habit. Trees ask you to apply it to a structure that calls itself.

A tree question also fits neatly into a small space. An interviewer can draw seven nodes on a whiteboard, mutate one pointer, and ask a question that has a real answer. That economy is why trees keep appearing.

When you meet one, do not reach for a remembered solution. Reframe the question in two parts:

What is true about every node here?
What do I need back from each subtree?

Those two questions carry you through depth, path, subtree comparison and validation problems. The Python interview questions walkthrough covers explaining trade-offs in a language you may be asked to use.

Start by Naming the Shape and the Invariant

Before you write anything, say what kind of tree you are looking at and why it matters. This takes ten seconds and prevents most wrong answers.

Say which tree you have

General binary tree. Each node has at most two children. No ordering promise.
Binary search tree. A left subtree holds smaller values and a right subtree holds larger ones.
Balanced. Balanced trees are defined so that height stays logarithmic in the node count; the intuition is that the tree does not degenerate into a chain.
Complete. Every level is full except possibly the last, which fills from the left.

A question about finding the smallest value is trivial on a search tree and requires a full scan on a general one. If you assume the wrong shape, everything downstream is wrong.

State the invariant out loud

An invariant is the property you rely on at every node. For a search tree: every value in a left subtree is smaller than the node, and every value in a right subtree is larger. Note the word subtree. The invariant is a property of the whole subtree, not just the immediate children. That distinction is exactly what the validation question below turns on. Also note that whether the ordering is strict or non-strict depends on the definition you are working with: some definitions allow equal values on one side, and some forbid duplicates entirely. Say which convention you are using before you rely on it.

Saying the invariant aloud does two things. It shows the interviewer you know why your algorithm is correct, and it gives you something to check yourself against when you get lost.

Traversal Order Is a Reasoning Tool, Not a Recital

Most candidates can recite preorder, inorder and postorder. Fewer can say which one they need and why. In a binary trees coding interview, the traversal choice is often the whole answer. Treat the three orders as three answers to a single question: when do I need the current node relative to its children?

The three depth-first orders

Preorder visits the node before its children. Use it when the parent's decision must be made first, such as copying a tree or passing a bound downward.
Inorder visits the left subtree, the node, then the right. On a search tree this yields sorted order, which converts many tree questions into sorted-array questions.
Postorder visits the children first. Use it when the node's answer depends on results from below, such as depth, height or subtree sums.

Level-order when the question is about layers

When the question mentions depth, width, or the nearest node at a level, a breadth-first traversal with a queue is the natural fit. It processes nodes layer by layer, which makes "which level am I on" explicit instead of implicit. The same principle — the structure you choose determines what you can ask cheaply — runs through our rate limiter system design walkthrough.

Before you write a line of code, say the sentence: "I am choosing postorder because each node needs its children's depths before it can compute its own." That single sentence is often worth more to the interviewer than the code that follows.

Worked Example: Maximum Depth, Reasoned Aloud

Take the question: given the root of a binary tree, return its maximum depth. Throughout this article, depth and height are used in the node-counting convention: a single node has depth one, and an empty tree has depth zero. Some texts count edges instead, which shifts every value by one; if you use that convention, say so once and stay consistent.

Step 1 — Restate and clarify. "So the depth is the number of nodes on the longest path from the root down to a leaf. Let me confirm: an empty tree returns zero, and a single node returns one."

Step 2 — Sketch. Draw a four-node tree: a root, a left leaf child, and a right child that has one leaf child of its own. Small enough to trace by hand, large enough to show the recursion.

Step 3 — Define the contract. "For any node, its depth is one plus the larger depth of its two children. If a child is missing, its depth is zero."

Step 4 — Identify base case and combine step. The base case is a missing node returning zero. The combine step is one plus the maximum of the two recursive results.

Step 5 — Trace the stack. Walk the sketch aloud. The root calls its left child, which calls two missing children and returns one. Then the root calls its right child, which calls its own leaf child (returning one) and a missing child (returning zero), so the right child returns two. The root takes the larger of one and two, adds one, and returns three. Narrating the unwinding is what proves you understand recursion rather than pattern-matching it.

Step 6 — Mention the alternative. "This is depth-first and recursive. There is also an iterative breadth-first version that counts levels with a queue, which I would prefer if the tree were deep enough that I worried about stack depth." That one sentence shows range without derailing the answer.

Worked Example: Validate a Binary Search Tree

This is the question that separates memorised answers from reasoned ones.

Why the obvious check is wrong

Many candidates write a function that compares each node with its two children and returns false if the ordering is violated. That is wrong. Picture a root of 10, a left child of 5, and a right child of 15. Now give the 5 a right child of 12. Every parent-child pair is locally ordered, but 12 sits in the left subtree of 10, so the tree is not a valid search tree. The flaw is that the check never looks beyond one level.

The bound-carrying fix

Carry a lower and an upper bound down the recursion. At the root the bounds are negative and positive infinity. When you descend left, the current node's value becomes the new upper bound. When you descend right, it becomes the new lower bound. A node is valid only if it sits strictly inside its inherited range. Every node is then compared against the whole ancestry, not just its parent.

The inorder alternative

An inorder traversal of a valid search tree produces values in ascending order. So you can traverse inorder while remembering the previous value and check that each new value is larger. This approach is often shorter to write and easier to explain under time pressure. The place candidates slip is the previous-value state: initialise it to a sentinel that is smaller than any real value (or track a "first node seen" flag), and decide up front whether your definition allows duplicates, since some BST definitions permit equal values on one side and some forbid them entirely.

Comparing the two live

Bounds: more explicit about the invariant, no extra state beyond the recursion, slightly more parameters to track.
Inorder: fewer moving parts, but relies on the reader accepting the sorted-order property, and you must handle the previous-value state and the duplicate policy carefully.

Either is defensible. Say which you are choosing and why, and the interviewer will follow you.

Talking About Time and Space Complexity

Complexity is where honest candidates stand out, because the space answer for trees is genuinely more interesting than the time answer. In a binary trees coding interview, this is also the part most candidates rush.

Time

Most tree traversals are linear in the number of nodes, because every node is visited once. Say that plainly: "This is O(n) time, since each node is processed exactly once." Do not hedge when the answer is simple.

Space

The auxiliary space is the depth of the recursion stack, which is proportional to the height of the tree. (Stack depth is height plus one in the node-counting convention, but that off-by-one is immaterial to big-O.) When the tree is balanced, height stays logarithmic in the node count, so the stack is O(log n). A skewed tree, where each node has only one child, has height proportional to the node count, so the stack is O(n).

Stating the worst case without hedging

The honest phrasing is: "Space is O(h) where h is the height, which is O(log n) when balanced and O(n) in the worst case." That is more accurate than claiming logarithmic space outright, and interviewers notice the difference.

Auxiliary versus input

Auxiliary space is what your algorithm allocates beyond the input. The tree itself already occupies memory before your function runs, so it does not count toward your auxiliary space. If an interviewer probes this distinction, they are checking whether you know what you are measuring. Answer directly.

Common Traps and How to Recover Mid-Answer

The traps

Forgetting the base case. Every recursion needs a stopping condition. For trees it is usually a missing node.
Mutating when the question implies read-only. If the question says "return" rather than "modify", do not rewire pointers.
Off-by-one depth counts. Decide early whether depth counts nodes or edges, and stay consistent.
Losing your place. After three recursive calls it is easy to forget which subtree you are in.

The recovery script

If you notice a flaw, stop. Do not push on and hope the interviewer misses it. Say something like: "Hold on, I think my check is wrong. Consider a left child of 5 with a right child of 12 under a root of 10. My local comparison passes but the tree is invalid. Let me carry bounds down instead."

That paragraph does more for your candidacy than a flawless recitation would. It shows you test your own reasoning and correct it under pressure, which is the skill the question is actually measuring. A caught mistake is evidence of reasoning, not failure.

When you get lost rather than wrong, redraw the tree and re-anchor on the current node. "Let me redraw this and mark where I am." Interviewers expect this.

Practising Binary Tree Reasoning Out Loud

Reading solutions builds recognition. Speaking solutions builds the skill the interview measures. Here is a routine that works.

Rehearse with a whiteboard or a plain text editor. No autocomplete, no syntax highlighting. Narrate each decision as you make it: "I am choosing postorder here because..."
Record yourself. Then review one thing only: did your explanation match the code you actually wrote? Mismatches are where the confusion lives.
Rotate a small set of patterns. Traversal, depth, path, subtree comparison, and search-tree bounds. These patterns recur often enough to be worth drilling.
Re-derive rather than recall. When you revisit a pattern, close the notes and rebuild it from the invariant. If you cannot, you memorised it rather than learned it.
Carry the habit sideways. The same structure — name the shape, state the invariant, choose the traversal, trace the stack — applies to graphs, dynamic programming and recursion generally.

Rehearsing out loud and then reviewing whether your explanation matched your code is the kind of practice that builds real confidence. When you return to a binary trees coding interview question, practise it out loud and review the recording honestly; that review is where the improvement happens.

What to Take Away

Binary tree questions reward reasoning, not recall. Name the shape of the tree and the invariant you will rely on. Choose a traversal order because of what each node needs from its children, and say so. Trace the call stack on a sketch before you commit to code. State time as linear and space as the height of the stack, and be honest about the worst case. And if you catch a flaw mid-answer, say so, show the counterexample, and correct it — that is the behaviour interviewers are actually scoring.

Practise a handful of core patterns out loud until the reasoning becomes automatic, and the next binary trees coding interview question will feel less like a test of memory and more like a conversation about structure.

Frequently asked questions

Do I need to memorise binary tree algorithms for a coding interview?

No. Memorised solutions collapse the moment a question is varied, and interviewers vary them deliberately. What you need is a repeatable reasoning habit: name the shape, state the invariant, choose a traversal order because of what each node needs from its children, and trace the recursion on a sketch.

What is the difference between a binary tree and a binary search tree in an interview answer?

A binary tree only promises that each node has at most two children. A binary search tree adds an ordering invariant: every value in a left subtree is smaller than the node, and every value in a right subtree is larger. Whether the ordering is strict or non-strict depends on the definition you are working with, so name that convention. Say which tree you have before you design anything.

How do I explain time and space complexity for a recursive tree solution?

Time is usually linear in the number of nodes, because each node is visited once. Space is the depth of the recursion stack, which is proportional to the height of the tree: O(log n) when balanced, O(n) in the worst case of a skewed tree. Phrase it as O(h) with both cases named.

What should I do if I get stuck halfway through a binary tree question?

Stop and say so rather than pushing on. If you have found a flaw, name it, give a small counterexample, and describe the correction. If you have simply lost your place, redraw the tree and re-anchor on the current node.

Is recursion always the right approach for binary tree problems?

No. Recursion is the natural fit when each node's answer depends on results from its subtrees, such as depth, height or subtree sums. An iterative breadth-first traversal with a queue is better when the question is about levels, width or the nearest node at a given depth, and it avoids deep call stacks on a skewed tree.

Rehearse tree reasoning out loud and review it against your code.