Tree Problems

Nine classic interview problems on binary trees — Invert a Binary Tree, Maximum Depth, Diameter, Same Tree, Level Order Traversal, Validate a Binary Search Tree, Kth Smallest in a BST, Lowest Common Ancestor and Serialize & Deserialize — solved from zero. For each one you get the slow obvious idea, the insight that fixes it, Algoistan pseudocode, tested Dart, and an animation you can feed your own tree: type a list such as 6, 2, 9, null, 4 and watch the tree being drawn, the calls piling up on the call stack or the nodes waiting in a queue, with every step saying why. By the end you will know the two moves almost every tree question is built from — let a recursive call answer for a subtree, or walk level by level with a queue — and when to pass information down instead of returning it up.

Trees, recursion and how to attack a tree question

Some words first. Each one comes back on every problem below.

• A tree is a set of nodes (boxes holding a value) joined by edges (links), with no loops. A binary tree is a tree where every node has at most two children, called left and right.
• The root is the node at the top: the only node with no parent. A node's children are the nodes directly below it; it is their parent. A leaf is a node with no children.
• A subtree is a node together with everything below it. The left child is the root of the left subtree. This is the key idea: a subtree is itself a tree, so whatever works for the whole tree works for each subtree.
• The depth of a node is how many edges you walk down from the root to reach it (the root has depth 0). The height of a tree, as used on this page, is the number of nodes on its longest path from the root down to a leaf — 0 for an empty tree, 1 for a single node. Written h.
• An empty tree is a root that is null: there are no nodes at all. Every missing child is an empty tree too.
• A binary search tree (BST) is a binary tree with a sorting rule: for every node, every value in its left subtree is smaller and every value in its right subtree is bigger. Three of the problems use this rule.
• O(n) means the work grows in step with the number of nodes n; O(h) means it grows with the height. See C03 · Growth of Functions.

A node in Dart, and how a tree is written in a question

Interviews give you this class (or ask you to write it). TreeNode? with a question mark means "a TreeNode or null" — a missing child has to be allowed (D05 · Null Safety). The tree itself lives on the heap (the shared storage room for objects); a variable like root holds only a reference — an arrow — to the top node, just like the list nodes of Step 13.6 · Linked List Problems, except that each node now has two arrows instead of one.

Questions write a tree as a level-order list: the values row by row from the top, each row from left to right, with null for a missing child. [6, 2, 9, null, 4, 7, 12] means: the root is 6; its children are 2 and 9; 2 has no left child (null) and a right child 4; 9 has the children 7 and 12. Only nodes that exist get child spots, so a null never has children written for it, and nulls at the very end are usually left out. The two helpers below turn such a list into nodes and back. Every test on this page uses them.

Reading the list needs a queue (a first-in, first-out waiting line, Queue from dart:collection — D28 · Stack, queue, deque): every node created waits in the queue until the next two values in the list are handed to it as its children. Type your own list and watch:

Recursion on trees: trust the call, and make null the base case

Recursion means a function that calls itself on a smaller piece of the problem (D07 · Recursion). On a tree the smaller pieces are obvious: the left subtree and the right subtree. Three rules make recursive tree code easy to write and easy to trust:

1. The base case is the empty tree. Start with if (node == null) return …; — what is the answer for no nodes at all? (0 nodes, depth 0, "yes it is valid", an empty list.) Handling null first means you never write node.left! and a leaf needs no special case: its two children are simply two empty trees.
2. Trust the recursive call. Do not trace the whole tree in your head. Assume f(node.left) already returns the correct answer for the left subtree, and the same for the right. Your only job is the one line that combines the two answers with the current node.
3. Know what the call stack costs. Each waiting call sits on the call stack (the pile of unfinished function calls). The pile is as tall as the deepest path, so recursion on a tree uses O(h) extra space: about log₂ n for a bushy, balanced tree, but n for a tree that is one long chain. A chain of 100 000 nodes can overflow the stack, which is when the loop-and-queue versions below matter.

Depth-first search (DFS) is the name for "go all the way down one side before trying the other". A recursive walk is a DFS, and it reaches every node at three moments: before going into its children, between the two children, and after both. Writing the value down at each moment gives the three classic orders:

An edge case: a tree that is one long chain to the right. The stack grows as tall as the tree has nodes — this is the O(h) space with h = n.

Breadth-first search: level by level with a queue

Breadth-first search (BFS) visits the tree row by row: the root, then all nodes at depth 1, then depth 2, and so on. A queue does it: take the node at the front, look at it, and put its children at the back. Because children always join behind everyone already waiting, a whole level is finished before the next one starts. BFS is the tool when the question mentions levels, rows, "closest", or "the first leaf" — Level Order Traversal below animates it. The same idea on general graphs is in C22 · Breadth-first search.

Space. DFS keeps one stack entry per level of the current path: O(h). BFS keeps one queue entry per node of the widest level: up to about n / 2 for a full tree. Neither is always smaller.

Return a value up, or pass a value down

Every recursive tree solution moves information in one of two directions, and choosing the direction is most of the thinking:

• Return a value up (bottom-up, postorder): each call answers a question about its own subtree — its size, height, sum, whether it is balanced — and the parent combines the children's answers. Maximum Depth and Diameter work this way.
• Pass a value down (top-down, preorder): each call is told something about the path above it — its depth, the sum so far, the biggest value seen, the range a BST value must fit in — and hands an updated version to its children. Validate BST works this way.

Invert a Binary Tree

The task. You get the root of a binary tree. Turn it into its mirror image — as if you held it up to a mirror standing beside it — so that every node's left and right children trade places, all the way down. Change the existing tree and return its root.

Brute force. Build a second, mirrored tree: a new node for the root whose left is the mirror of the old right subtree and whose right is the mirror of the old left. It is already O(n) time, but it creates n new nodes (O(n) extra memory) and leaves the original tree unchanged, which is not what was asked.

Key insight. Mirroring a tree is the same job at every node: swap its two children, then mirror each of the two subtrees. A subtree is a smaller tree, so "mirror each subtree" is the recursive call. The base case: an empty tree is its own mirror. The order does not matter — swapping first and then recursing, or recursing first and then swapping, both work — as long as each node is swapped exactly once.

Why it is correct. The recursive call returns a correctly mirrored subtree (trust it). After the swap, the mirrored old right subtree hangs on the left and the mirrored old left subtree on the right — which is exactly the definition of the mirror of the whole tree.

An edge case: a chain that leans left. After mirroring it leans right; each node's single child just changes sides.

Without recursion. The same swaps can be done in any order, so a queue (BFS) works too, and it avoids a deep call stack on a long chain:

Complexity. Time O(n) — one swap per node. Space O(h) for the recursion (h up to n for a chain); the BFS version uses O(width of the widest level).

Follow-ups interviewers ask. Check whether a tree is its own mirror — Symmetric Tree (p07-q6). Do it without recursion (the BFS version above). Compare a tree with the mirror of another without building the mirror.

The idea underneath: recursion and the call stack — D07 · Recursion — and changing objects through references, D22 · Variables, objects and references.

Maximum Depth of a Binary Tree

The task. You get the root of a binary tree. Return its maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has maximum depth 0; a single node has 1.

Brute force. Walk every path from the root to a leaf, keep each path as a list, and return the length of the longest. Correct, but each path is copied as it grows, so on a deep tree the work is about n · h, and the paths take memory too.

Key insight — return a value up. The deepest path from a node goes through its deeper child. So the depth of a tree is 1 (the node itself) plus the larger of its two subtrees' depths, and an empty subtree has depth 0. The answer for a node needs both children's answers first: this is a postorder walk.

Why it is correct. Any path from the node down to a leaf starts with the node and then continues entirely inside one subtree. The longest such path therefore has length 1 + (the longest path in the left subtree) or 1 + (the longest in the right) — and the recursive calls return exactly those two lengths.

An edge case: a chain to the right. Every node has one empty side that answers 0, so each level adds exactly one — and the call stack grows as tall as the tree.

Counting levels with BFS. Process the queue one whole level at a time and count the levels. No recursion, so no risk of a deep stack:

Complexity. Time O(n) — each node is visited once and does O(1) work. Space O(h) for the recursion; O(width) for the BFS queue.

Follow-ups interviewers ask. Minimum depth — the closest leaf (p07-q9). Is the tree height-balanced (p07-q7)? Diameter, the next problem, uses the same returned heights.

The idea underneath: bottom-up recursion, D07 · Recursion; tree height and why balanced search trees keep it near log₂ n, C12 · Randomly built binary search trees.

Diameter of a Binary Tree

The task. You get the root of a binary tree. Return the length of its longest path between any two nodes, counted in edges. The path may go up and then down, and it does not have to pass through the root.

Brute force. For every node, compute the heights of its two subtrees from scratch and add them; take the best. Each height computation walks a whole subtree, so on a chain the total is about n² / 2.

Key insight — return one thing, remember another. Every path has one highest node where it bends. The longest path bending at node goes down the deepest path on the left and the deepest path on the right: height(left) + height(right) edges (with height counted in nodes, the two counts are exactly the number of edges on each side, including the edge to the child). So one postorder pass does it: each call returns its subtree's height to its parent (that is what the parent needs), and meanwhile updates best, a variable outside the recursion, with the path bending here (that is what the question asks). The returned value and the answer are different things — the heart of many hard tree problems.

Why it is correct. Every path has exactly one highest node, so checking "the best path bending here" at every node checks every possible path's best version. A parent can only extend one side of a child's path upward, which is why the call returns 1 + max(l, r), not l + r.

An edge case: the longest path does not pass through the root. The root's own bending path has only 4 edges; the best, 5, was found earlier at node 2 and kept in best.

Complexity. Time O(n) — each node is visited once. Space O(h) for the call stack.

Follow-ups interviewers ask. Maximum path sum, where values can be negative (p07-q21 — the same "return one side, remember both sides" shape). The longest path whose nodes all hold the same value. The diameter of a general tree with many children: keep the two largest child heights.

The idea underneath: the same returned heights as Maximum Depth, plus a best-so-far variable captured by a nested function (a closure — D07 · Closures).

Same Tree (and Subtree)

The task. You get the roots of two binary trees, p and q. Return true if they are the same: the same shape, and the same value in every matching position. Otherwise return false.

Brute force. Serialize both trees, with a marker for every empty spot so that shape is recorded (the last problem on this page), and compare the two strings. It works, but it always does all the work and builds two strings of about 2n tokens, even when the roots already differ.

Key insight. Walk both trees together, one pair of matching nodes at a time. Two trees are the same exactly when: both are empty; or both are non-empty, the roots hold the same value, the two left subtrees are the same, and the two right subtrees are the same. That sentence is the code. Dart's && stops at the first false (short-circuit evaluation), so the walk ends at the first difference.

Why it is correct. The definition of "the same tree" is itself recursive — same root value, same left subtree, same right subtree — and the base cases cover every way a pair can be empty: both (same) or just one (different shape).

An edge case: same values, different shape. The roots match; then the left pair is (7, empty) — one spot is empty and the other is not, so the answer is false and the right pair is never examined.

Follow-up: Subtree of Another Tree. Is sub exactly equal to some node's whole subtree inside root? Try isSameTree at every node of root: O(n · m) for trees of n and m nodes. The full solution, with an O(n + m) idea, is question p07-q11.

Complexity. Time O(n) where n is the smaller tree's size (the walk stops at the first difference). Space O(h).

Follow-ups interviewers ask. Symmetric tree — compare the left subtree with the mirror of the right one, pairing outer with outer (p07-q6). Subtree of another tree (p07-q11). Flip-equivalent trees: the same if you may swap children at any nodes — check both pairings at each node.

The idea underneath: walking two structures in lockstep, like merging two lists in Step 13.6 · Merge Two Sorted Lists; identity versus equality in D29 · Object (==, hashCode).

Level Order Traversal

The task. You get the root of a binary tree. Return its values level by level: a list of lists, where the first inner list is the root's value, the next holds the values at depth 1 from left to right, and so on.

Brute force. Find the height h, then for each depth d from 0 to h − 1 walk the whole tree and collect the nodes at depth d. Correct, but the tree is walked h times: O(n · h).

Key insight. BFS with a queue visits nodes in exactly level order. The only extra trick is keeping levels apart: at the start of each round, the queue holds exactly one whole level, so read its length into size before taking anything, and take exactly that many nodes. The children they add are the next level, waiting behind.

Why it is correct. Invariant: when a round starts, the queue holds all nodes of depth d, left to right, and nothing else. Taking those size nodes and adding their children (left before right) leaves all nodes of depth d + 1 in left-to-right order — the same fact for the next round.

An edge case: the empty tree. The first line returns an empty list at once; the queue is never created.

Complexity. Time O(n) — each node joins and leaves the queue once. Space O(n) for the answer, and up to the widest level (about n / 2 in a full tree) for the queue.

Follow-ups interviewers ask. Zigzag order — every second level right to left (p07-q14). Right side view — the last node of each level (p07-q13). Average of each level (p07-q20). Minimum depth — stop at the first leaf (p07-q9).

The idea underneath: breadth-first search, C22 · Breadth-first search, and Dart's queue, D28 · ListQueue inside: the ring buffer.

Validate a Binary Search Tree

The task. You get the root of a binary tree. Return true if it is a valid binary search tree: for every node, all values in its left subtree are strictly smaller than the node's value, and all values in its right subtree are strictly bigger. (Equal values are not allowed.) An empty tree is valid.

The trap: checking only the children. The tempting code compares each node with its own two children. It accepts Example 2: 12's left child 6 is smaller than 12, so the check passes — yet 6 is in the right subtree of 8. The rule is about whole subtrees, not neighbours.

Brute force. Check the rule literally: at every node, list all values of the left subtree and make sure each is smaller, list the right subtree and make sure each is bigger. Correct, but every value is examined once for every ancestor: O(n · h), which is O(n²) for a chain.

Key insight — pass a window down. Each node's value must lie in an open window (low, high). The root's window is unlimited. Going left from a node with value v, everything must be smaller than v, so the window becomes (low, v); going right, it becomes (v, high). Each node checks only its own value against the window it was given — one comparison per node. Dart's int? with null meaning "no limit" avoids picking a fake smallest or largest number.

Why it is correct. The window handed to a node is exactly the set of values allowed by all its ancestors: each ancestor it lies left of gives an upper fence, each ancestor it lies right of gives a lower fence, and keeping only the tightest fence on each side loses nothing. So a node passes its check exactly when it respects every ancestor — the definition of a BST.

The edge case from Example 2: 6 passes the check against its parent but fails its window (8, 12).

Another O(n) way. An inorder walk of a BST lists the values in increasing order (left subtree, node, right subtree — C12 · The BST property & inorderWalk). So walk inorder and check that every value is bigger than the one before:

Complexity. Time O(n). Space O(h) for the recursion.

Follow-ups interviewers ask. Two values of a BST were swapped by mistake: fix the tree (p07-q26 — the inorder walk shows one or two "drops"). Insert into and delete from a BST (p07-q12, p07-q19). Build a balanced BST from a sorted list (p07-q10).

The idea underneath: the BST property and inorder walks, C12 · Binary Search Trees; passing information down as parameters, the opening section.

Kth Smallest Element in a BST

The task. You get the root of a binary search tree and a number k (1 ≤ k ≤ number of nodes). Return the k-th smallest value in the tree, counting from 1.

Brute force. Walk the whole tree inorder into a list (it comes out sorted, because the tree is a BST) and return element k − 1. Always O(n) time and O(n) memory, even when k is 1.

Key insight — inorder with an explicit stack, stop early. An inorder walk produces the values smallest first, so the k-th value it produces is the answer. Doing the walk with our own stack instead of recursion makes stopping trivial: just return. The walk is: slide left as far as possible, pushing every node passed (each one is bigger than everything to its left, so it must wait); pop the top — it is the smallest value not counted yet; count it; then continue in its right subtree, which holds the values just above it.

Why it is correct. The stack always holds the nodes whose left side is finished but which are not counted yet, smallest on top. Popping a node and then sliding down its right subtree visits exactly the values between it and the next node on the stack, in order — so values come out sorted and the k-th pop is the k-th smallest.

An edge case: k = 1 on a tree leaning left. The walk slides all the way down, the first pop is the answer, and nothing on the right side is ever looked at.

Complexity. Time O(h + k) — sliding down costs up to h, then each counted value costs O(1) on average. Space O(h) for the stack.

Follow-ups interviewers ask. The tree changes often and kth is asked often: store the size of each subtree in its node, then walk down choosing left or right by the sizes in O(h) (p07-q23). The k-th largest: walk in reverse inorder (right, node, left). The successor of a value without parent links.

The idea underneath: inorder walks of a BST, C12 · inorderWalk, done with a stack as in Step 13.4 · Stack Problems; subtree sizes for order statistics, C14 · Augmenting Data Structures.

Lowest Common Ancestor

The task. You get the root of a tree and two of its nodes, p and q. Return their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree. A node counts as being in its own subtree, so if p is above q, the answer is p. Interviews ask two versions: on a BST, and on an ordinary binary tree.

Brute force (works on any tree). Find the path from the root to p and the path from the root to q. Both start at the root and share a beginning; the last shared node is the LCA. Two searches, O(n) time, plus the memory for two paths.

Version 1: the tree is a BST

Key insight. In a BST the values tell you where p and q are. At a node with value v: if both p and q are smaller than v, both are in the left subtree, so their LCA is there too — go left. If both are bigger, go right. Otherwise they are on different sides (or one of them is v itself), so this node is the first one that contains both: it is the answer. No recursion, no stack: a single walk down.

Why it is correct. While both values are on the same side, every common ancestor is on that side too, so nothing is lost by going there. At the first node where they split, any deeper node lies entirely on one side and cannot contain both — so this node is the lowest one that does.

An edge case: one node is an ancestor of the other. At node 10 the target 10 is not smaller than 10, so "both smaller" fails, and 10 is returned.

Version 2: any binary tree

Key insight — return what you found. Without the sorting rule we must search, and we search both sides at once. Each call answers "what did you find in your subtree?": null if neither p nor q is there; the node p or q if exactly one was found (or the node itself is p or q); or the LCA if both were found below. At a node: if the left side found something and the right side found something, p and q are on different sides, so this node is the LCA. If only one side found something, pass that up unchanged.

Why it is correct. If the node itself is p, the answer is p whether or not q is below it (p is then an ancestor of q, or q is elsewhere and a higher node will see p from one side and q from the other). When both sides report something, they must be p and q (values are distinct and each side can report only what it contains), so this node is the deepest one containing both. Otherwise the LCA, if it exists below, is reported up by the one side that found anything.

An edge case: p is an ancestor of q. The call at 6 returns 6 immediately without searching below — and that is already the right answer.

Complexity. BST version: time O(h), space O(1). General version: time O(n) (every node may be visited), space O(h) for the recursion.

Follow-ups interviewers ask. Nodes have parent links: walk up from both — the same trick as finding where two linked lists meet. Many queries on a fixed tree: precompute "binary lifting" tables. All nodes at distance k from a target (p07-q25 — uses parent links built by one walk).

The idea underneath: searching a BST, C12 · Querying a binary search tree; returning results up the call stack, the opening section.

Serialize & Deserialize a Binary Tree

The task. Write two functions. serialize(root) turns a binary tree into a String; deserialize(data) turns that string back into a tree with exactly the same shape and values. Any format is allowed, as long as the round trip gives back the same tree. (Sending a tree over a network, or saving it to a file, needs exactly this.)

Why values alone are not enough. Writing just the preorder values loses the shape: [4, 7] and [4, null, 7] both give "4,7". Writing preorder and inorder values identifies a tree only when all values are distinct (p07-q17). With duplicates allowed, the format must record where the empty spots are.

Key insight. Write the tree in preorder, and write a marker # for every empty spot. Preorder puts each node before its subtrees, so the reader always learns about a node before it needs to attach anything to it. To read: take the next token; if it is #, this spot is empty; otherwise make a node, then read its left subtree (the very next tokens), then its right subtree. The reader follows exactly the same recursion as the writer, so it consumes the tokens in the order they were written.

Why it is correct. By induction on the tree: serialize writes a subtree as one contiguous block — the root, the left subtree's block, the right subtree's block — and deserialize reads exactly one such block per call, so each call rebuilds exactly the subtree that was written there. The empty tree's block is the single token #.

An edge case: the empty tree. write(null) runs once and the whole string is #.

And the other direction: type a string of tokens and watch the tree grow, each token landing in the next empty spot that preorder says comes next.

An edge case for reading: a single node. The first token makes the node; the next two tokens are both #, so both children stay empty.

The level-order format works too. The input format used throughout this page — level order with null — is also a complete serialization; toLevelOrder and fromLevelOrder at the top of the page are the two halves. Preorder with markers is shorter to code recursively; level order is easier for people to read.

Complexity. Both functions: time O(n), space O(n) for the string and O(h) for the recursion.

Follow-ups interviewers ask. Serialize a BST without markers — the BST rule restores the shape from preorder values alone (p07-q24). Rebuild a tree from preorder and inorder lists (p07-q17). Use as few characters as possible: binary encoding, or level order with trailing nulls dropped.

The idea underneath: preorder walks and recursion; strings and splitting in Dart, D24 · String methods; JSON as a general serialization format, D19 · Files, JSON & HTTP.

Quiz

Interview questions

Variations and follow-ups of the nine problems above. Trees in prompts and examples are written as level-order lists with null for a missing child, exactly like the inputs of the animations. Every solution is tested in Dart on its examples and on hundreds of random trees against a slow reference.

Cheat sheet

Start every tree function with the null case, decide whether information flows up or down, and test four trees: empty, one node, a chain, and a full tree. Recursion costs O(h) stack — h can be n.