Binary Trees & BSTs

Why this pattern exists / recognition signals

A binary tree is a linked structure like a linked list, but each node has up to two “next” pointers (left, right) instead of one — that branching is what lets it represent hierarchy (file systems, expression parsing, decision logic) instead of a flat sequence. A binary search tree (BST) adds one ordering invariant on top: for every node, everything in its left subtree is smaller, everything in its right subtree is larger. That single invariant is what turns “search a tree” from O(n) into O(log n) when balanced — at every node you eliminate one entire subtree from consideration, the same halving intuition as binary search on a sorted array, just realized as pointers instead of index arithmetic.

Recognition signals — reach for tree thinking when the problem says:

“binary tree” / TreeNode input → traversal-based recursion is almost always the first move
“validate a BST” / “kth smallest in a BST” / “closest value” → BST invariant + inorder traversal
“lowest common ancestor” → recursive divide-and-conquer on subtrees, or parent-pointer + set intersection
“level by level” / “level order” / “zigzag” / “right side view” → BFS with a queue
“serialize/deserialize” / “path sum” / “diameter” → DFS with return values carried back up the recursion
Any variant of “is this tree balanced/valid/symmetric” → recursive check that compares/combines information from both children

Core mechanism

The three DFS orders, on a concrete tree

DFS visits by going as deep as possible before backtracking; the three classic orders differ only in when you visit the current node relative to recursing into its children.

Preorder (root, left, right): 4, 2, 1, 3, 6, 5, 7 — visit the node on the way down. Useful for copying/serializing a tree (you can rebuild it top-down from this order).
Inorder (left, root, right): 1, 2, 3, 4, 5, 6, 7 — visit the node between its children. On a BST specifically, this always yields values in sorted order (see below).
Postorder (left, right, root): 1, 3, 2, 5, 7, 6, 4 — visit the node on the way back up. Useful whenever a node needs information from both children first (tree height, diameter, deleting/freeing a tree bottom-up).

flowchart TD
    N4["4"] --> N2["2"]
    N4 --> N6["6"]
    N2 --> N1["1"]
    N2 --> N3["3"]
    N6 --> N5["5"]
    N6 --> N7["7"]

sequenceDiagram
    participant Stack as call stack (recursion)
    Note over Stack: Inorder(4): recurse left first
    Stack->>Stack: Inorder(2): recurse left first
    Stack->>Stack: Inorder(1): no children, visit 1
    Stack->>Stack: back at 2, visit 2
    Stack->>Stack: Inorder(3): no children, visit 3
    Stack->>Stack: back at 4, visit 4
    Stack->>Stack: Inorder(6): recurse left first
    Stack->>Stack: Inorder(5): no children, visit 5
    Stack->>Stack: back at 6, visit 6
    Stack->>Stack: Inorder(7): no children, visit 7
    Note over Stack: final order: 1,2,3,4,5,6,7

BFS / level-order traversal

BFS visits the tree row by row, left to right, using a queue (not a stack — this is the single most common preorder/BFS mix-up). Push the root; repeatedly pop the front, visit it, push its children.

flowchart LR
    subgraph Level0["level 0"]
        A4["4"]
    end
    subgraph Level1["level 1"]
        B2["2"]
        B6["6"]
    end
    subgraph Level2["level 2"]
        C1["1"]
        C3["3"]
        C5["5"]
        C7["7"]
    end
    A4 --> B2
    A4 --> B6
    B2 --> C1
    B2 --> C3
    B6 --> C5
    B6 --> C7

Visit order: 4, 2, 6, 1, 3, 5, 7 — the queue’s FIFO discipline is exactly what guarantees each level finishes before the next one starts: everything enqueued while processing level k is, by construction, level k+1, and it can’t be dequeued until every remaining level-k node has been.

Why inorder-of-a-BST is sorted, and why balance matters

The BST invariant (left < node < right, recursively, for every node) means: when inorder visits “left subtree, then node, then right subtree,” it’s visiting everything smaller than this node, then this node, then everything larger — recursively true at every level, so the whole traversal comes out fully sorted. This isn’t a coincidence of the example tree above; it’s a direct consequence of the invariant.

Balance matters because a BST’s O(log n) search/insert/delete guarantee assumes the tree’s height is O(log n). Nothing in the plain BST insert rule enforces that — inserting 1, 2, 3, 4, 5 in sorted order into a BST with no rebalancing produces a tree that’s just a right-leaning chain, structurally identical to a singly linked list, degrading every operation to O(n):

flowchart TD
    T1["1"] --> T2["2"]
    T2 --> T3["3"]
    T3 --> T4["4"]
    T4 --> T5["5"]
    Note["inserting sorted input with no rebalancing
produces height n, not log n — search degrades to O(n)"]

Self-balancing BSTs (AVL trees, Red-Black trees) fix this by enforcing a height/balance invariant on every insert/delete — AVL keeps every node’s left/right subtree heights within 1 of each other (tighter balance, faster lookups, slower writes due to more frequent rotations); Red-Black trees allow more slack (looser balance, faster writes, slightly slower lookups) via a color-based invariant. Both guarantee O(log n) height without requiring you to derive the rotation logic to use the guarantee in an interview — naming them and stating what problem they solve is usually sufficient unless rotations are explicitly asked for.

Worked numeric example — validate a BST

Tree to validate:

The naive mistake: checking only node.left.val < node.val < node.right.val locally at each node — this misses violations where a deeper descendant breaks the bound of an ancestor further up, not just its immediate parent. The correct approach passes down a valid (min, max) range that tightens as you descend.

Node visited	incoming range (low, high)	node.val	in range?	recurse left with	recurse right with
5 (root)	(-inf, +inf)	5	yes	(-inf, 5)	(5, +inf)
3	(-inf, 5)	3	yes	(-inf, 3)	(3, 5)
1	(-inf, 3)	1	yes	(-inf, 1)	(1, 3)
1’s children	—	null	base case, valid	—	—
7	(3, 5)	7	no — 7 > 5	—	—

Result: invalid — 7 is greater than its subtree’s upper bound of 5 (inherited from being in root 5’s right branch, but node 3’s right child still can’t exceed 5, the ancestor bound), even though 7 > 3 looks locally fine. This is exactly the bug a local-only check misses.

Java — representative implementations

import java.util.*;
 
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 
public class TreeOps {
 
    // Validate BST — pass down a tightening (min, max) range
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
 
    private boolean validate(TreeNode node, long low, long high) {
        if (node == null) return true; // empty subtree is trivially valid
        if (node.val <= low || node.val >= high) return false;
        return validate(node.left, low, node.val)
            && validate(node.right, node.val, high);
    }
 
    // Lowest Common Ancestor — general binary tree (no BST invariant assumed)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root; // found one of the targets, or hit the bottom
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root; // p and q found in different subtrees -> this is the LCA
        }
        return (left != null) ? left : right; // both in one subtree, or neither found
    }
 
    // Level-order traversal (BFS)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // snapshot: exactly this level's nodes
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

Python — representative implementations

from collections import deque
from typing import Optional
 
 
class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def is_valid_bst(root: Optional[TreeNode]) -> bool:
    """Validate BST — pass down a tightening (low, high) range."""
 
    def validate(node: Optional[TreeNode], low: float, high: float) -> bool:
        if node is None:
            return True  # empty subtree is trivially valid
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and validate(
            node.right, node.val, high
        )
 
    return validate(root, float("-inf"), float("inf"))
 
 
def lowest_common_ancestor(
    root: Optional[TreeNode], p: TreeNode, q: TreeNode
) -> Optional[TreeNode]:
    """LCA — general binary tree (no BST invariant assumed)."""
    if root is None or root is p or root is q:
        return root  # found one of the targets, or hit the bottom
 
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root  # p and q found in different subtrees -> this is the LCA
    return left if left else right  # both in one subtree, or neither found
 
 
def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    """Level-order traversal (BFS)."""
    result: list[list[int]] = []
    if root is None:
        return result
 
    queue = deque([root])
    while queue:
        level_size = len(queue)  # snapshot: exactly this level's nodes
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Complexity comparison

Operation	Balanced BST	Unbalanced/degenerate BST	Notes
Search	O(log n)	O(n)	Degenerate case behaves like a linked list
Insert	O(log n)	O(n)	Same reasoning
Delete	O(log n)	O(n)	Delete of a node with two children needs an inorder predecessor/successor swap
DFS traversal (any order)	O(n) time, O(h) space	O(n) time, O(n) space	`h` = height; recursion stack depth = height, so O(log n) balanced vs O(n) degenerate
BFS / level order	O(n) time, O(w) space	O(n) time, O(w) space	`w` = max width of a level, can be up to O(n) even in a balanced tree
Find min/max	O(log n) (leftmost/rightmost)	O(n)	Only valid on a BST, not a general binary tree

Common pitfalls

Validating a BST by only checking immediate children: node.left.val < node.val < node.right.val misses violations from a deeper descendant that breaks an ancestor’s bound — always thread a tightening (min, max) range down the recursion.
Confusing BFS (queue) with DFS preorder (stack/recursion): both can produce a “root-ish first” visiting flavor, but only BFS guarantees strict level-by-level order — using recursion when the problem needs “level by level” output is a common mismatch.
Forgetting to snapshot queue.size() before the inner loop in level-order BFS: without capturing the level’s size first, the inner loop’s termination condition gets contaminated by children being enqueued mid-loop, merging levels together.
Recursion depth on very deep/degenerate trees: a DFS solution recurses to depth = tree height; on a degenerate (linked-list-shaped) tree with e.g. 100,000 nodes, this can blow the call stack — worth mentioning an iterative-with-explicit-stack alternative when input isn’t guaranteed balanced.
LCA: assuming BST structure when the tree is a general binary tree (or vice versa): the BST version can use the ordering invariant to decide direction in O(log n) without visiting both children; the general binary tree version can’t skip subtrees and must actually search both sides, which is a materially different (and more expensive) algorithm — don’t apply the BST shortcut to a tree that isn’t guaranteed sorted.
Off-by-one / wrong base case in “empty tree” handling: an empty tree (null root) is a valid BST, has height 0 (or -1, depending on convention — state your convention explicitly), and terminates recursion — a missing or wrong base case here breaks nearly every recursive tree function.

Practice problems

Validate Binary Search Tree (tightening range)
Lowest Common Ancestor of a Binary Tree / of a BST (general vs BST-optimized versions)
Binary Tree Level Order Traversal (BFS with a queue)
Binary Tree Zigzag Level Order Traversal (BFS, alternate direction per level)
Kth Smallest Element in a BST (inorder traversal, stop early at the kth visit)
Binary Tree Maximum Path Sum (postorder, carry a “best path through this node” value back up)
Diameter of Binary Tree (postorder, height + diameter computed together)
Serialize and Deserialize Binary Tree (preorder with null markers, or BFS-based)
Balanced Binary Tree (postorder height check, short-circuit on first imbalance found)

Interview angles

“Why does inorder traversal of a BST come out sorted — prove it, don’t just state it.” — the BST invariant recursively guarantees “everything left is smaller, everything right is larger” at every node, so visiting left-subtree-then-node-then-right-subtree recursively visits smaller-before-this-before-larger at every level, which composes into a fully sorted sequence.
“Your BST is unbalanced — what actually breaks, and how would you know?” — every O(log n) guarantee (search/insert/delete) silently degrades to O(n) because it’s really “O(height),” not O(log n) — the fix is a self-balancing structure (name AVL or Red-Black) or, if the whole dataset is known upfront, building a balanced tree directly from sorted data.
“AVL vs Red-Black — when would you pick one over the other?” — AVL is more tightly balanced (faster reads, more rotations on writes) — good for read-heavy workloads; Red-Black allows looser balance (fewer rotations, faster writes) — good for write-heavy workloads; most language standard libraries (e.g. Java’s TreeMap, C++‘s std::map) use Red-Black trees for this reason.
“LCA without parent pointers vs with parent pointers — how does the approach change?” — without parent pointers: recursive divide-and-conquer, checking whether p and q are found in different subtrees (that node is the LCA) or the same subtree (recurse deeper). With parent pointers: walk both nodes’ ancestor chains into sets and find the first shared ancestor — trades recursion for extra space, but avoids re-deriving structure.
“What’s the space complexity of your recursive DFS solution, really?” — the call stack itself is O(h) auxiliary space (h = tree height), which people often forget to state — it’s O(log n) for a balanced tree but O(n) worst case, exactly mirroring the search-time balance argument.
“How would you serialize a tree so you can perfectly reconstruct it later?” — preorder traversal with explicit null markers (so structure, not just values, is recoverable) is the standard answer; inorder alone is insufficient because it doesn’t uniquely determine tree shape without a second traversal order.

Notes

Explorer