Trees interview questions

Tree problems are recursion problems in disguise. Once you can say what a function returns for one node, given the answers for its children, the rest is writing it down.

How do I solve trees interview questions?

Tree problems are solved by recursion on one node: define what the function returns for a subtree, combine the results from the left and right children, and handle the empty case. Use depth-first search for paths and structure, breadth-first search with a queue for levels, and the ordering property for binary search trees.

Practise trees

How to recognise a trees problem

The input is a binary tree or a binary search tree and the question asks for depth, balance, a path, a lowest common ancestor, a level view or validity.

The answer for a node depends on the answers for its two children.

A question says level by level, or the view from the side, which points to breadth-first search.

How to build the solution

Write the base case first: an empty node returns the neutral value (zero depth, true for valid, null for found nothing).

Decide whether information flows up (each call returns a result, like height) or down (each call receives a constraint, like the allowed range for a valid binary search tree), or both.

For level-order problems, use a queue and process one level at a time by taking the queue's current size.

For binary search trees, use the ordering: an in-order walk visits values in sorted order, and search follows one branch.

Classic problems to practise

Maximum Depth of Binary Tree, Invert Binary Tree, Validate Binary Search Tree, Lowest Common Ancestor, Binary Tree Level Order Traversal, Diameter of Binary Tree, Serialize and Deserialize Binary Tree, Kth Smallest Element in a BST.

Mistakes interviewers see

Checking a binary search tree by comparing a node only to its children. Every node must respect the bounds set by all its ancestors.

Forgetting the empty tree and returning wrongly for a leaf, which is a node with two empty children.

Mixing up a path that must go down from a node with one that can bend through it, which changes the answer in problems like maximum path sum.

Not stating the recursion depth: on a skewed tree it equals the number of nodes, which can overflow the stack.

Practise it as an interview

Take a topic-based interview on trees to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.

Frequently asked questions

Depth-first or breadth-first?

Depth-first for paths, structure and anything that depends on the children's answers. Breadth-first for level-by-level questions and shortest-distance questions in an unweighted structure.

What is the time complexity of a tree traversal?

Linear in the number of nodes, since each node is visited once. Space is the height of the tree for recursion, or the widest level for breadth-first search.