Binary Search Tree & In-order

At a glance

The instinct

A binary search tree is a sorted array folded into a tree: everything in a node's left subtree is smaller, everything in the right subtree is larger. Two consequences drive almost every BST question:

1. In-order traversal (left, node, right) produces values in ascending order. Any "sorted array" trick - compare with the previous element, count to k, find the closest pair - works on the in-order stream.
2. A comparison at a node tells you which half to ignore. Searching, inserting, finding a floor/ceiling or the lowest common ancestor costs O(h), like binary search.

If an interviewer hands you a BST and you write a solution that ignores the ordering, they usually expect you to do better.

Recognise it

Not this pattern if...

• It is a plain binary tree without ordering - use general Tree DFS/BFS.
• You need dynamic floor/ceiling on a changing set of keys but nobody gave you a tree - reach for a library ordered set (TreeMap).
• The question is about heights, paths or shapes rather than values - ordering does not help.

Memory hack

Analogy - a library shelf turned sideways. Pick any book: every title to its left on the shelf comes earlier alphabetically, every one to its right comes later. Reading the shelf left to right (in-order) gives the catalogue in order, and to find a title you never scan the whole shelf - each glance tells you which side to walk.

Say it out loud in the interview:

1. "It's a BST, so in-order gives sorted values and each comparison prunes a side."
2. "Do I need the sorted stream (prev / counter / iterator) or a directed walk (search, LCA, bounds)?"
3. "Duplicates and extremes: is the ordering strict, and do I need long or null bounds?"

How it works

Iterative in-order uses a stack to simulate the call stack: slide left as far as possible pushing nodes, pop one (it is the next smallest), then move into its right subtree and repeat. This lets you stop early (kth smallest), pause (BST iterator) or compare with the previous value (validate, minimum difference).

flowchart TD
  A["cur = root"] --> B{"cur != null or stack not empty?"}
  B -->|no| Z["done"]
  B -->|yes| C["push cur and go left until null"]
  C --> D["node = pop() -- next value in sorted order"]
  D --> E["visit: compare with prev, count k, emit..."]
  E --> F["cur = node.right"]
  F --> B

Trace of Kth Smallest Element in a BST with k = 3 on 5 -> (3, 6), 3 -> (2, 4):

Java template

import java.util.*;

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class BstTemplates {
    // 1) Iterative in-order: the sorted stream with early exit.
    static int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        Integer prev = null;                         // previous value, for "compare with neighbour" problems
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) { stack.push(cur); cur = cur.left; }
            TreeNode node = stack.pop();
            // visit(node): e.g. validate -> if (prev != null && node.val <= prev) return false;
            if (--k == 0) return node.val;
            prev = node.val;
            cur = node.right;
        }
        throw new IllegalArgumentException("k larger than tree size");
    }

    // 2) Bounds (the "fence"): every node must sit strictly inside (low, high).
    static boolean isValid(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return isValid(node.left, low, node.val) && isValid(node.right, node.val, high);
    }
    // call: isValid(root, Long.MIN_VALUE, Long.MAX_VALUE)

    // 3) Directed walk: O(h) LCA / search / floor-ceiling style.
    static TreeNode lca(TreeNode root, int p, int q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p < cur.val && q < cur.val) cur = cur.left;
            else if (p > cur.val && q > cur.val) cur = cur.right;
            else return cur;                         // split point (or equal to one of them)
        }
        return null;
    }
}

// 4) Lazy iterator: O(h) memory, amortised O(1) next().
class BstIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();
    BstIterator(TreeNode root) { pushLeft(root); }
    boolean hasNext() { return !stack.isEmpty(); }
    int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }
    private void pushLeft(TreeNode n) { while (n != null) { stack.push(n); n = n.left; } }
}

Complexity

h is O(log n) for a balanced tree but O(n) for a degenerate one (keys inserted in sorted order). Morris traversal brings in-order to O(1) extra space by temporarily threading right pointers.

Variations

• Sorted-stream with prev - compare neighbours. Minimum Absolute Difference in BST, Minimum Distance Between BST Nodes, Validate Binary Search Tree, recover two swapped nodes.
• Rank / early stop - Kth Smallest Element in a BST; for kth largest use reverse in-order (right, node, left).
• Pausable traversal - Binary Search Tree Iterator; two iterators (ascending + descending) give two-sum on a BST.
• Directed descent - Lowest Common Ancestor of a Binary Search Tree, search, insert, floor/ceiling, closest value.
• Build from sorted data - pick the middle as root for a height-balanced tree. Convert Sorted Array to Binary Search Tree.
• Range pruning - skip subtrees outside [low, high], e.g. range sum or trimming a BST.

Common mistakes

• Using Integer.MIN_VALUE / MAX_VALUE as sentinels when node values can equal them - use long bounds or null.
• Allowing equal values when the problem defines a strict BST (<= vs <), or vice versa when duplicates are permitted on one side.
• Doing a full traversal and building a list for kth smallest when an early-exit in-order needs only O(h + k).
• Assuming O(log n) - a BST built from sorted input is a linked list; say "O(h)" and qualify it.
• In the iterator, pushing the whole tree in the constructor (O(n) memory) instead of only the left spine.

All practice problems

7 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.