Trees & BST

DFS recursion, BFS layer traversal, and the BST invariant that makes search, insert, delete all O(log n).

intermediatePractice Full theoryPrereq:Recursion Fundamentals

Start practice Read the theory See all problems

What you'll learn

Traverse a tree preorder, inorder, postorder (DFS) and level-order (BFS)
Write the universal DFS recursion template for tree problems
Exploit the BST invariant for O(log n) search, insert, and validation
Know why inorder traversal of a BST yields sorted order
Find the lowest common ancestor in a general tree and a BST
Explain how balance affects complexity (O(log n) balanced vs O(n) skewed)

When to reach for this

Signals (use it)

Hierarchical/nested data: file systems, org charts, expression trees
"Traverse / sum / find depth / check balance" of a tree
Sorted data with frequent insert/delete and order queries → BST
"Lowest common ancestor", "kth smallest in BST"
Shortest path / level-by-level → BFS on the tree

Anti-signals (don't)

Flat sequential data → array/list
Need O(1) lookup by key without order → hash map
Graph with cycles → graph algorithms (trees are acyclic)

Theory & deep dive

A tree is a hierarchy of nodes, each with a value and links to its children; a binary tree limits that to a left and right child. Trees are where recursion pays off most: nearly every tree problem is solved by the same move — do something with the current node, then recurse into the children and combine — because a tree is literally defined in terms of smaller trees.

The star of this module is the binary search tree (BST): a binary tree with one invariant — everything in the left subtree is smaller, everything in the right is larger. That single rule turns search, insert, and delete into O(log n) operations on a balanced tree, and makes an in-order traversal spit out values in sorted order.

This module covers the traversal orders (and what each is good for), the DFS recursion template, BFS level-order, lowest common ancestor, and the BST operations — with the complexity caveat that an unbalanced tree degrades everything to O(n).

The big idea in plain words

A tree is like an org chart: one boss at the top, and each person has a few people reporting below them. A binary search tree adds one tidy rule - smaller values go left, bigger values go right - so finding something becomes a guided search that drops half the remaining people at every step.

Example: in a binary search tree, reading the nodes in the order left-then-node-then-right (called an inorder walk) spits everyone out already sorted, for free. So a question like 'find the 3rd smallest value' turns into 'walk inorder and stop at the 3rd one' - no sorting step needed, because the tree's shape already encodes the order.

Tree vocabulary

Term	Meaning
Root	The top node, no parent
Leaf	A node with no children
Height	Longest root-to-leaf edge count
Depth	Edges from the root to a given node
Balanced	Left/right heights differ by ≤ 1 everywhere → O(log n) height
BST invariant	left subtree < node < right subtree, recursively
Complete	All levels full except possibly the last, filled left-to-right (heaps)

The word balanced is doing heavy lifting: a balanced binary tree has height ~log n, so traversing a root-to-leaf path is O(log n). A degenerate (skewed) tree is really a linked list with height n.

The four traversals and when to use each

DFS visits a whole branch before backtracking; the three DFS orders differ only in when you process the current node relative to its children.

Traversal	Order	Best for
Preorder	node, left, right	copy/serialize a tree, prefix expressions
Inorder	left, node, right	BST → sorted output, kth smallest
Postorder	left, right, node	delete/free a tree, compute heights, bottom-up DP
Level-order (BFS)	level by level	shortest path, level sums, right-side view

Memorise: inorder of a BST is sorted. That fact alone solves 'kth smallest', 'validate BST', and 'two-sum in BST'.

The universal DFS template

Almost every tree problem fits one recursive shape: handle the empty (null) base case, recurse left and right, then combine. Whether you're computing depth, summing values, or checking balance, only the 'combine' step changes.

Java· Max depth (postorder combine)

int maxDepth(TreeNode root) {
    if (root == null) return 0;          // base case
    int left = maxDepth(root.left);      // recurse
    int right = maxDepth(root.right);
    return 1 + Math.max(left, right);    // combine
}

BFS level-order on trees

Use a queue and process one level at a time by snapshotting the queue size before each level loop. BFS is the natural fit for anything 'per level': level averages, right-side view (last node of each level), minimum depth, and zigzag traversal.

Python· Level-order traversal

from collections import deque

def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out

BST operations and the invariant

The BST invariant lets you discard half the tree at each step, exactly like binary search. To search, go left if the target is smaller, right if larger. Insert follows the same path to the empty slot. Validate by checking that every node lies within an inherited (min, max) range — not just that its immediate children compare correctly.

Python· Validate a BST with min/max bounds

def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
    if not node:
        return True
    if not (lo < node.val < hi):
        return False
    return (is_valid_bst(node.left,  lo, node.val) and
            is_valid_bst(node.right, node.val, hi))

Watch out

Validating a BST by only comparing a node to its direct children is WRONG — a deep descendant can violate the invariant. Pass down (min, max) bounds, or do an inorder traversal and check it's strictly increasing.

Lowest common ancestor

The LCA of two nodes is the deepest node that has both as descendants. In a general binary tree, recurse: if the current node is one of the targets, return it; otherwise look left and right — if both sides return non-null, the current node is the LCA. In a BST, it's even easier: walk down, and the LCA is the first node whose value lies between the two targets (the split point).

Tip

For a BST LCA, you don't need to search both subtrees: if both targets are smaller, go left; both larger, go right; otherwise this node is the split point and the LCA. O(log n) on a balanced tree.

How to talk about this in the interview

“State the traversal you'll use and why: "This needs bottom-up information — a child's height before the parent's — so I'll use postorder DFS." For BST problems, invoke the invariant: "Because left < node < right, I can binary-search the tree, and an inorder traversal gives me sorted order for free." Always give complexity in terms of balance: "O(h) where h is the height — O(log n) if balanced, O(n) worst case if the tree is skewed."”

Common mistakes

–Validating a BST by comparing only to immediate children instead of inherited min/max bounds
–Forgetting the null base case in tree recursion → NullPointerException
–Quoting O(log n) for BST ops without noting it degrades to O(n) on a skewed tree
–Not snapshotting queue size in BFS, so levels bleed together
–Confusing height (down to leaf) with depth (down from root)
–Using preorder when the problem needs bottom-up (postorder) information

Complexity summary

Tree traversals (DFS or BFS) are O(n) time visiting every node, with O(h) space for the recursion stack / O(w) for the BFS queue (h = height, w = max width). BST search/insert/delete are O(h): O(log n) balanced, O(n) worst case when skewed.

Practice problems

41 total