Trees

Binary trees and binary search trees: the recursive contract, the four traversal orders, BST ranges and lowest common ancestor, each traced on a small tree.

Overview

A tree is a set of nodes joined by edges, with one node at the top (the root) and exactly one path from the root to every other node. There are no cycles. A binary tree is a tree where each node has at most two children, called left and right. Most tree problems use binary trees.

Nearly every tree problem is solved the same way: decide what a call on one node should return, get that answer from the left and right subtrees, and combine the two. If you can state that contract out loud, the code is short.

The words you need

The examples on this page all use the same seven-node tree. It is also a binary search tree, which the BST section uses.

Root — the one node with no parent — 4
Leaf — a node with no children — 1, 3, 5, 7
Subtree — a node plus everything below it — 2 with 1 and 3
Depth of a node — edges from the root down to it — depth of 3 is 2
Height of the tree — edges on the longest root-to-leaf path — 2

Some problems count nodes instead of edges (LeetCode's Maximum Depth counts nodes, so the answer there is 3). Check which one the problem means.

The recursive contract

A recursive tree function has three parts: a base case for an empty subtree, two recursive calls, and a line that combines the results.

For maximum depth, the contract is 'return the number of nodes on the longest path down from here'. An empty subtree returns 0, and a node returns 1 plus the larger child answer. The trace shows the order in which calls finish on the sample tree.

1 — 1 — 0 — 0 — 1
2 — 3 — 0 — 0 — 1
3 — 2 — 1 — 1 — 2
4 — 5 — 0 — 0 — 1
5 — 7 — 0 — 0 — 1
6 — 6 — 1 — 1 — 2
7 — 4 — 2 — 2 — 3

Each node is visited once, so the time is O(n). The call stack holds one frame per level, so the extra space is O(h), where h is the height.

Information flows down or up

There are two ways to move information through a tree, and naming which one you use is the first step.

Top-down — something known about its ancestors — Path Sum, Count Good Nodes, Validate BST
Bottom-up — answers from both children first — Maximum Depth, Balanced Binary Tree, Diameter, LCA
Both — a value passed down and a value returned — Path Sum III, Sum Root to Leaf Numbers

The four traversal orders

Depth-first search (DFS) goes as deep as it can before backing up. The three DFS orders differ only in when the node itself is visited: before, between or after its two subtrees. Breadth-first search (BFS), also called level order, visits the tree one level at a time.

Preorder — before both subtrees — 4, 2, 1, 3, 6, 5, 7 — copying a tree, serializing it, top-down problems
Inorder — between left and right — 1, 2, 3, 4, 5, 6, 7 — BSTs: it gives the keys in sorted order
Postorder — after both subtrees — 1, 3, 2, 5, 7, 6, 4 — heights, sums, deleting a tree, bottom-up problems
Level order — one level at a time — [4], [2, 6], [1, 3, 5, 7] — anything that says level, row, width or nearest

All four visit every node once: O(n) time. DFS keeps a stack as deep as the tree, O(h). BFS keeps a queue as wide as the widest level, which reaches (n + 1)/2 nodes, about half the tree, at the last level of a perfect tree.

Level order with a queue

BFS puts the root in a queue. Each round, it reads how many nodes are in the queue now: that is exactly one level. It removes that many nodes and adds their children.

1 — [4] — 1 — [4] — [2, 6]
2 — [2, 6] — 2 — [2, 6] — [1, 3, 5, 7]
3 — [1, 3, 5, 7] — 4 — [1, 3, 5, 7] — []

The queue must remove from the front cheaply. In Python, collections.deque removes from the front in O(1), while list.pop(0) moves every other element. In JavaScript, Array.prototype.shift moves every remaining element, so a loop of shifts can cost O(n^2) on a wide tree; build each next level in a new array, or keep a read index, instead.

Binary search trees

A binary search tree (BST) is a binary tree where every key in a node's left subtree is smaller than the node, and every key in its right subtree is larger. The rule is about whole subtrees, not just the two children.

Search, insert and delete follow one path from the root, so they cost O(h). That is O(log n) when the tree is balanced and O(n) when it degrades into a chain, for example after inserting keys in sorted order. Self-balancing trees (AVL, red-black) keep h at O(log n); Java's TreeMap is a red-black tree and guarantees log(n) time for get, put and remove.

The classic mistake in Validate BST is to compare a node only with its parent. The tree below passes that local check at every node and is still not a BST.

The fix is top-down: pass each node the open range its key must fall in. Going left tightens the upper bound; going right tightens the lower bound.

5 — (-inf, +inf) — yes
3 — (-inf, 5) — yes
7 — (5, +inf) — yes
4 — (5, 7) — no: return False

An inorder walk works too: a tree is a BST exactly when its inorder sequence is strictly increasing. Here it reads 3, 5, 4, 7, 8, and 4 after 5 gives it away.

Lowest common ancestor

The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both of them in its subtree (a node counts as its own descendant). The bottom-up contract is 'return p or q if you found one below you, else None'.

The table traces p = 3 and q = 5 on the sample tree, in the order the calls finish.

1 — None — None — None
3 — stops early — stops early — 3 (it is q or p)
2 — None — 3 — 3
5 — stops early — stops early — 5
7 — None — None — None
6 — 5 — None — 5
4 — 3 — 5 — 4: the LCA

This version is O(n) time and assumes both nodes are in the tree. In a BST you can do better: walk down from the root, going left while both keys are smaller and right while both are larger; the first node that splits them is the LCA, in O(h).

Recursion depth

Recursive DFS uses one stack frame per level. On a balanced tree that is about log2(n) frames, which is nothing. On a skewed tree of 100,000 nodes it is 100,000 frames. CPython stops at its recursion limit (see sys.getrecursionlimit()) with a RecursionError, and Java throws StackOverflowError when the thread stack runs out.

Balanced — about log2(n) — small — recursion is fine
Skewed (a chain) — n - 1 — n frames — use an explicit stack, or BFS

> [!TIP] > Say the space as O(h) and then name both cases: O(log n) balanced, O(n) skewed. It shows you know where the stack comes from.

What you will be able to do

State the recursive contract for a tree problem: base case, what each call returns, how two answers combine.
Choose between top-down and bottom-up, and between DFS and BFS, and say why.
Write all four traversals, recursively and with an explicit stack or queue.
Validate a BST with ranges and explain why the parent-only check fails.
Find the lowest common ancestor in a binary tree in O(n) and in a BST in O(h).

When to use it

The data is a hierarchy: parent and child, folder and file, manager and report
You must visit every node once and combine answers from subtrees
The input is a BST and you need ordered data: sorted walk, kth smallest, floor or ceiling
The question asks about paths: root to leaf, or between any two nodes
You must rebuild a tree from traversals or serialize one to a string
The question says level, row, width, depth or nearest leaf (use BFS)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio