Binary Search Trees

Binary search, but the sorted array can grow and shrink in O(log n).

intermediate~75 min7 simulations12 problems

▶ guided lesson ⚡ 1-minute summary ↻ 14 recall cards

before this: Tree Recursion · Binary Search · Recursion

Section

01 · why it exists

Why this exists, and the weight it carries

since1960–62

Binary search tree

P. F. Windley; A. D. Booth & A. J. T. Colin; Thomas N. Hibbard — independently

Around 1960 several researchers arrived at the same idea on their own: keep keys in a tree where smaller keys go left and larger keys go right. Windley (The Computer Journal, 1960) and Booth with Colin (Information and Control, 1960) built such trees one key at a time. Hibbard's 1962 paper in the Journal of the ACM studied these trees mathematically, for searching and sorting, and gave a way to delete keys from them.

the problem it solvedA dictionary you can search like a sorted list, yet grow one key at a time without shifting everything after it.

its jobs today

Ordered maps and sets: Java's TreeMap/TreeSet are balanced BSTs, so keys come back sorted and floor/ceiling queries are O(log n).
"Nearest key" questions in apps: the next booking after 10:30, the highest bid below ₹500, the previous version before a timestamp.
The base idea of database indexes: B-trees and B+-trees are BSTs widened to many keys per node.

the weight it carries

Illustrative: 10 lakh (1,000,000) keys. A balanced BST is ⌊log₂ 1,000,000⌋ + 1 = 20 levels deep, so a search makes at most 20 comparisons. Insert the same keys in sorted order into a plain BST and you get a chain 1,000,000 levels deep. A sorted array also searches in 20 steps, but inserting at the front shifts all 1,000,000 elements.

without it

You'd choose between a sorted array (fast search, O(n) inserts) and a hash table (fast inserts, no order) — nothing would give you both, plus "next bigger key", in O(log n).

when · why · how

when: You need sorted order or nearest-key questions while keys are being added and removed.
why: Search, insert, delete, floor and ceiling all walk one root-to-leaf path: O(h) — O(log n) when balanced — versus O(n) inserts for a sorted array and no order at all in a HashMap.
how: Given a TreeNode, walk with cur = x < cur.val ? cur.left : cur.right. In real code use TreeMap/TreeSet (see the TreeMap card in the Java toolkit chapter).

since1962

BST delete with the in-order successor (Hibbard deletion)

Thomas N. Hibbard

Inserting into a BST is easy; deleting a node with two children is not — its slot needs a value that fits between both subtrees. Hibbard's 1962 JACM paper proposed the answer still taught today: replace the node by its in-order successor, the smallest key in its right subtree. Sedgewick and Wayne's Algorithms calls it Hibbard deletion, and notes its flaw: always using the successor is not symmetric, so long runs of random deletes and inserts make the tree lopsided.

the problem it solvedRemoving any key — even one with two children — while keeping every BST promise, in time proportional to the height.

its jobs today

Java's TreeMap.deleteEntry does exactly this: a node with two children gets its successor's key and value, then the successor is removed and the tree rebalanced.
The standard hand-written BST delete — the LC 450 interview classic — uses the successor (or the mirror, the predecessor).

the weight it carries

Illustrative: delete one key from a balanced BST of 10 lakh keys. Hibbard deletion walks to the node and on to its successor — both on one root-to-leaf path of at most 20 nodes. Flatten-and-rebuild visits all 1,000,000 nodes twice: 2,000,000 node visits.

without it

Deleting would mean rebuilding the tree, or leaving "deleted" markers behind that slow down every later search.

when · why · how

when: LC 450 or any "implement a BST" round — the two-children case is what the interviewer is checking.
why: O(h): the successor has no left child, so removing it is always the easy 0-or-1-child case. The predecessor works just as well.
how: Copy succ.val into the node, then root.right = deleteNode(root.right, succ.val) — always assign the returned subtree back.

since1962

Self-balancing BST (AVL tree)

Georgy Adelson-Velsky & Evgenii Landis

A plain BST is fast only while it stays bushy; sorted input turns it into a chain. In 1962 two Soviet mathematicians, Adelson-Velsky and Landis, published "An algorithm for the organization of information" in Doklady Akademii Nauk SSSR — the AVL tree. Its rule: at every node the two subtree heights differ by at most 1, restored after each update by rotations. Later designs relaxed the rule; the red-black tree behind Java's TreeMap is one (see the TreeMap card in the Java toolkit chapter).

the problem it solvedGuaranteeing O(log n) search, insert and delete whatever order the keys arrive in.

its jobs today

Keeping ordered maps fast on bad input: timestamps and auto-increment ids arrive already sorted, the worst case for a plain BST.
Balanced trees (AVL or red-black) sit under every TreeMap-style API: sorted maps, ordered sets, interval and calendar lookups.

the weight it carries

Illustrative: 10 lakh keys inserted in sorted order. Plain BST: a chain — up to 1,000,000 comparisons per search. AVL: height < 1.4405·log₂(1,000,002) − 0.3277 ≈ 28.4, so at most 28 comparisons. Red-black (TreeMap): height ≤ 2·log₂(1,000,001) ≈ 39.9, about 40. Perfect balance: 20.

without it

Any BST fed sorted or nearly sorted keys would quietly decay into a linked list, and every operation into O(n).

when · why · how

when: Whenever keys may arrive in sorted or nearly sorted order — in real systems (ids, timestamps) that's common.
why: A rotation is O(1) and only nodes on the update path need fixing, so staying balanced costs O(log n) per update while every operation stays O(log n).
how: Don't hand-code it in interviews unless asked: TreeMap<K, V> / TreeSet<E> give you a red-black tree. Know the rule (heights differ by ≤ 1) and that rotations keep the inorder order.

02 · plain english

The idea in 30 seconds

A BST is a binary tree with one promise: everything left of a node is smaller, everything right is larger — at every node, not just its children.

So searching is binary search: compare, then throw away a whole side. Cost = the height h, which is O(log n) when the tree is balanced.

Read it in order (left → node → right) and you get the values sorted. Java's TreeMap/TreeSet are self-balancing BSTs that guarantee O(log n).

picture this

Your phone's contact list, searched by halves: open the middle, "Priya" is after "Neha", so drop the first half. A BST stores those halving checkpoints as nodes — so adding Rahul only hangs one new node at the bottom, instead of shifting every name after him.

03 · remember

What you must know

BST property: for every node, all values in its left subtree < node < all values in its right subtree. Checking only the direct children is not enough.
Inorder traversal of a BST is sorted. Many BST problems are just "inorder, with a twist" (validate, kth smallest, iterator, minimum difference).
Search / insert / delete all walk one root-to-leaf path: O(h). A balanced tree has h ≈ log₂ n; a degenerate one (sorted inserts) has h = n − 1.
Insert = search until you fall off the tree, then hang the new value there as a leaf.
Delete has 3 cases: leaf → unlink; one child → the child takes its place; two children → copy the in-order successor (leftmost node of the right subtree), then delete that successor (which has no left child).
Successor / floor / ceiling = a walk that remembers the best candidate on the way down: every node bigger than x is a candidate for "next larger", and each new one is closer.
Self-balancing BSTs (AVL, red-black) rotate after inserts/deletes to keep h = O(log n) always. Java's TreeMap and TreeSet are red-black trees — use them instead of writing your own.
Ordered queries are a BST's superpower over a HashMap: floor, ceiling, lower, higher, first, last, ranges — each O(log n) in a TreeMap.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Search — one path, half thrown away each step

Grey nodes are ruled out the moment we turn the other way. The number of comparisons is at most height + 1.

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode searchBST(TreeNode root, int val) {3        TreeNode cur = root;4        while (cur != null) {5            if (val == cur.val) return cur;6            if (val < cur.val) cur = cur.left;     // smaller → left7            else cur = cur.right;                  // larger → right8        }9        return null;                               // fell off the tree: not here10    }11}

sim

Insert — search, fall off, attach

The new value always becomes a leaf. Nothing else moves.

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode insertIntoBST(TreeNode root, int val) {3        TreeNode fresh = new TreeNode(val);4        if (root == null) return fresh;5        TreeNode cur = root;6        while (true) {7            if (val < cur.val) {8                if (cur.left == null) { cur.left = fresh; break; }9                cur = cur.left;10            } else {11                if (cur.right == null) { cur.right = fresh; break; }12                cur = cur.right;13            }14        }15        return root;16    }17}

sim

Delete with the in-order successor

Try a leaf, a node with one child, and the root (two children). Watch the successor's value move up.

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode deleteNode(TreeNode root, int key) {3        if (root == null) return null;                                       // key not found4        if (key < root.val) root.left = deleteNode(root.left, key);5        else if (key > root.val) root.right = deleteNode(root.right, key);6        else {7            // cases 1 & 2: zero or one child → the other side replaces this node8            if (root.left == null) return root.right;9            if (root.right == null) return root.left;10            // case 3: two children → copy the in-order successor, then delete it11            TreeNode succ = root.right;12            while (succ.left != null) succ = succ.left;                      // smallest on the right13            root.val = succ.val;14            root.right = deleteNode(root.right, succ.val);15        }16        return root;17    }18}

sim

Validate with (low, high) ranges

Every node shows the range its ancestors allow. The default tree looks fine locally but 3 sits on the right of 5.

loading simulation…

javajava.util.*

1class Solution {2    public boolean isValidBST(TreeNode root) {3        return valid(root, null, null);4    }5 6    /** Every value in this subtree must lie strictly between low and high (null = no limit). */7    private boolean valid(TreeNode node, Integer low, Integer high) {8        if (node == null) return true;9        if ((low != null && node.val <= low)10                || (high != null && node.val >= high)) return false;11        return valid(node.left, low, node.val)                           // left: new upper bound12                && valid(node.right, node.val, high);                    // right: new lower bound13    }14}

sim

Inorder successor — remember the best candidate

Every node bigger than p becomes the new "best so far" and we go left to look for a closer one. Try p = 45 (answer above it) and p = 30 (answer below it).

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {3        TreeNode successor = null;          // smallest value > p.val seen so far4        TreeNode cur = root;5        while (cur != null) {6            if (p.val < cur.val) {7                successor = cur;            // bigger than p: a candidate8                cur = cur.left;             // a smaller candidate can only be on the left9            } else {10                cur = cur.right;            // cur ≤ p: everything bigger is on the right11            }12        }13        return successor;                   // the last candidate is the closest one14    }15}

sim

BST iterator — inorder you can pause

The stack holds the left spine still to visit. Count the pushes at the end: one per node, however the calls are spread.

loading simulation…

javajava.util.*

1class BSTIterator {2    private final Deque<TreeNode> stack = new ArrayDeque<>();   // the left spine still to visit3 4    public BSTIterator(TreeNode root) {5        pushLeft(root);6    }7 8    private void pushLeft(TreeNode node) {9        for (; node != null; node = node.left) stack.push(node);10    }11 12    public int next() {13        TreeNode node = stack.pop();      // smallest value not yet returned14        pushLeft(node.right);             // its successor lives in the right subtree's left spine15        return node.val;16    }17 18    public boolean hasNext() {19        return !stack.isEmpty();20    }21}

sim

Degenerate vs balanced

Same values, different insertion order. Sorted input builds a stick; middle-first builds a bush.

loading simulation…

05 · cost

Time & space, explained

BST operations (n values, height h)
	Balanced (TreeMap / AVL)	Plain BST, worst case	why
Search / contains	O(log n)	O(n)	One comparison per level; a degenerate tree has n levels.
Insert	O(log n)	O(n)	Walk down to the empty spot. A red-black tree then needs at most 2 rotations (plus recolouring) to rebalance.
Delete	O(log n)	O(n)	Find the node, maybe walk to the successor — still one path down.
Min / max	O(log n)	O(n)	Keep going left (or right) to the end of the spine.
Successor / floor / ceiling	O(log n)	O(n)	A search that remembers the best candidate seen on the way down.
Inorder traversal (all values sorted)	O(n)	O(n)	Visits each node once; stack depth O(h).
Kth smallest (no extra data)	O(log n + k)	O(n)	Walk the left spine (h steps), then k pops of an inorder.
Build from a sorted array	O(n)	—	Each value becomes a node once; picking the middle keeps it balanced.

Choosing an ordered structure
	Lookup	Insert / delete	Ordered queries (floor, range, min)	why
Sorted array + binary search	O(log n)	O(n)	O(log n)	Fast to search, but inserting shifts everything to the right.
HashMap / HashSet	O(1) average	O(1) average	O(n) — no order	Hashing scatters keys, so "next larger key" means scanning everything.
TreeMap / TreeSet (red-black)	O(log n)	O(log n)	O(log n)	Height is guaranteed ≤ 2·log₂(n + 1).
Hand-written unbalanced BST	O(h)	O(h)	O(h)	Great to learn from; h can degrade to n with sorted input.

06 · java

Raw vs Collections Framework

The node is the same — the promise is new

javaTreeNodejava.util.*

1/** Same node as any binary tree — the BST rule is a promise about the values, not a new type. */2class TreeNode {3    int val;4    TreeNode left, right;5 6    TreeNode(int val) {7        this.val = val;8    }9 10    TreeNode(int val, TreeNode left, TreeNode right) {11        this.val = val;12        this.left = left;13        this.right = right;14    }15}

A BST uses the exact TreeNode from the binary trees chapters. "BST" is a rule about where values sit.
LeetCode BSTs have distinct values unless the problem says otherwise. If duplicates are allowed, pick a side (e.g. ≤ goes left) and stick to it — or store a count per node.

Your own BST vs TreeMap / TreeSet

javahand-written (unbalanced)java.util.*

1/** A minimal (unbalanced) BST of distinct ints. Every operation walks ONE root-to-leaf path: O(h). */2class Bst {3    private TreeNode root;4    private int size;5 6    boolean contains(int x) {7        TreeNode cur = root;8        while (cur != null) {9            if (x == cur.val) return true;10            cur = x < cur.val ? cur.left : cur.right;   // throw away half the tree11        }12        return false;13    }14 15    /** Returns false if x was already present (no duplicates). */16    boolean add(int x) {17        if (root == null) { root = new TreeNode(x); size++; return true; }18        TreeNode cur = root;19        while (true) {20            if (x == cur.val) return false;21            if (x < cur.val) {22                if (cur.left == null) { cur.left = new TreeNode(x); size++; return true; }23                cur = cur.left;24            } else {25                if (cur.right == null) { cur.right = new TreeNode(x); size++; return true; }26                cur = cur.right;27            }28        }29    }30 31    /** Smallest value: keep going left. (Largest: keep going right.) */32    int min() {33        if (root == null) throw new NoSuchElementException();34        TreeNode cur = root;35        while (cur.left != null) cur = cur.left;36        return cur.val;37    }38 39    /** Inorder of a BST = values in ascending order. */40    List<Integer> sorted() {41        List<Integer> out = new ArrayList<>();42        inorder(root, out);43        return out;44    }45 46    private void inorder(TreeNode node, List<Integer> out) {47        if (node == null) return;48        inorder(node.left, out);49        out.add(node.val);50        inorder(node.right, out);51    }52 53    /** Height in edges (-1 for an empty tree) — shows how lopsided the tree became. */54    int height() {55        return height(root);56    }57 58    private int height(TreeNode node) {59        return node == null ? -1 : 1 + Math.max(height(node.left), height(node.right));60    }61 62    int size() {63        return size;64    }65}

javaTreeMap / TreeSet ordered APIjava.util.*

1/** The ordered API you get for free from a red-black tree: every call below is O(log n). */2class OrderedApi {3    static void demo(List<String> log) {4        TreeMap<Integer, String> map = new TreeMap<>();5        map.put(10, "ten");6        map.put(20, "twenty");7        map.put(30, "thirty");8        map.put(40, "forty");9 10        log.add("floorKey(25)=" + map.floorKey(25));       // greatest key <= 25 → 2011        log.add("ceilingKey(25)=" + map.ceilingKey(25));   // least key >= 25 → 3012        log.add("lowerKey(20)=" + map.lowerKey(20));       // greatest key < 20 → 1013        log.add("higherKey(20)=" + map.higherKey(20));     // least key > 20 → 3014        log.add("floorKey(5)=" + map.floorKey(5));         // nothing <= 5 → null (not an exception!)15        log.add("first/last=" + map.firstKey() + "/" + map.lastKey());16        log.add("headMap(30)=" + map.headMap(30).keySet());          // keys < 30 (a live view)17        log.add("tailMap(30)=" + map.tailMap(30).keySet());          // keys >= 3018        log.add("subMap(15,35)=" + map.subMap(15, 35).keySet());     // 15 <= key < 3519 20        TreeSet<Integer> set = new TreeSet<>(List.of(5, 1, 9, 3));21        log.add("set=" + set);                                       // always sorted: [1, 3, 5, 9]22        log.add("set.ceiling(4)=" + set.ceiling(4));23        log.add("pollFirst=" + set.pollFirst() + " then " + set);    // removes the smallest24        log.add("descending=" + set.descendingSet());25    }26}

Write a BST by hand to understand it; in real code and most interviews use TreeMap / TreeSet. They are red-black trees: guaranteed O(log n), no degenerate case.
floorKey, ceilingKey, lowerKey, higherKey return null when no key qualifies — check before unboxing to int.
firstKey() / lastKey() throw NoSuchElementException on an empty map; firstEntry() / pollFirstEntry() return null instead.
headMap, tailMap, subMap are live views — cheap to create, O(k) to iterate, and writes go through to the original map. Their size() walks the range: O(k).
A TreeMap with natural ordering rejects null keys (NullPointerException).

Delete by hand: the three cases

javadelete with the in-order successorjava.util.*

1class Solution {2    public TreeNode deleteNode(TreeNode root, int key) {3        if (root == null) return null;                                       // key not found4        if (key < root.val) root.left = deleteNode(root.left, key);5        else if (key > root.val) root.right = deleteNode(root.right, key);6        else {7            // cases 1 & 2: zero or one child → the other side replaces this node8            if (root.left == null) return root.right;9            if (root.right == null) return root.left;10            // case 3: two children → copy the in-order successor, then delete it11            TreeNode succ = root.right;12            while (succ.left != null) succ = succ.left;                      // smallest on the right13            root.val = succ.val;14            root.right = deleteNode(root.right, succ.val);15        }16        return root;17    }18}

Leaf or one child: return the other child to the parent — the recursion re-links it for you (root.left = deleteNode(root.left, key)).
Two children: the successor is the smallest value larger than the node. It has no left child, so deleting it is always case 1 or 2.
Using the in-order predecessor (rightmost of the left subtree) is equally correct. Java's own TreeMap.deleteEntry does the same successor copy before rebalancing.

Java API you will actually use
call	does	cost
`map.put(k, v) / get(k) / remove(k)`	Basic TreeMap operations	O(log n)
`map.containsKey(k)`	Membership (TreeSet: `contains`)	O(log n)
`map.floorKey(k) / ceilingKey(k)`	Greatest key ≤ k / least key ≥ k (or null)	O(log n)
`map.lowerKey(k) / higherKey(k)`	Greatest key < k / least key > k (or null) — `higherKey` is the inorder successor	O(log n)
`map.floorEntry(k) / ceilingEntry(k)`	Same, but returns key and value together	O(log n)
`map.firstKey() / lastKey()`	Smallest / largest key (throws if empty)	O(log n)
`map.pollFirstEntry() / pollLastEntry()`	Remove and return the smallest / largest entry	O(log n)
`map.headMap(k) / tailMap(k) / subMap(a, b)`	Live views of keys < k / ≥ k / in [a, b)	O(log n) to start iterating, O(k) to walk
`set.ceiling(x) / floor(x) / higher(x) / lower(x)`	TreeSet versions of the same queries	O(log n)
`set.descendingSet() / map.descendingMap()`	Reverse-order view	O(1) to create
`new TreeMap<>(Comparator.reverseOrder())`	Custom ordering	O(1) to create

Fast lookups only, no order

→ HashMap / HashSet

O(1) average beats O(log n).

Sorted keys, or "closest key" / range queries

→ TreeMap / TreeSet

floor/ceiling/subMap in O(log n), always balanced.

A sliding window that needs its min/max or nearest value

→ TreeSet (or TreeMap of counts for duplicates)

Insert, remove and neighbour queries all O(log n).

Only the smallest/largest repeatedly

→ PriorityQueue (heaps chapter)

Simpler and faster constants than a TreeMap; no need for full order.

Static sorted data, many lookups, no inserts

→ Sorted array + Arrays.binarySearch

Less memory, cache-friendly, same O(log n).

The interviewer says "implement it yourself"

→ Hand-written BST (recursive or iterative)

Then state that it's O(h) and can degrade without balancing.

07 · recognise

Spot the pattern

The input is a BST and you need sorted order

Inorder traversal (iterative with a stack if you need to stop early)

"Validate" / "is this a BST"

Pass (low, high) down, or check inorder is strictly increasing

Find / insert / delete / closest value in a BST

Walk one path using comparisons: O(h), O(1) space iteratively

"Next larger" / "successor" / "previous smaller" of a node

Walk from the root remembering the best candidate (or TreeMap.higherKey)

LCA in a BST

Walk down while both values are on the same side; first split = LCA

"Closest value", "next larger", "previous smaller" in a changing set

TreeSet / TreeMap floor & ceiling

Intervals that must not overlap, bookings, merging on insert

TreeMap keyed by start; check floorEntry and ceilingEntry

Sliding window + "values within t of each other"

TreeSet window with ceiling(x − t), or buckets of width t + 1

Sorted array / list → tree

Middle element as root, recurse on both halves

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Checking only left.val < node.val < right.val — a grandchild can still break the rule (5 → right 6 → left 3).
Using Integer.MIN_VALUE / MAX_VALUE as range sentinels when node values can be exactly those — use Long bounds or null for "no limit".
Forgetting that BST values are usually strictly ordered: a duplicate makes the tree invalid in LC 98.
Assuming O(log n) for a hand-written BST: sorted inserts make it a linked list with O(n) operations.
In delete, forgetting to re-link the returned subtree (root.left = deleteNode(root.left, key)), so the deletion is lost.
Successor: returning the first node bigger than p instead of the last candidate on the walk — the first one is usually too big.
Unboxing a null from floorKey/ceiling into an int → NullPointerException.
Calling firstKey() on an empty TreeMap — it throws; use firstEntry() (returns null) or check isEmpty().
Overflow in range checks with large values (LC 220): compute differences in long.

tricks

First question in any BST problem: "is inorder enough?" — very often it is.
Say the complexity as O(h), then add: "O(log n) if balanced, O(n) if skewed — TreeMap guarantees the first."
Prefer the iterative walk for search/insert/LCA/successor: a few lines, O(1) extra space, no recursion depth issues.
For delete, draw the three cases before coding. Interviewers mostly want to hear "two children → successor".
When the problem says "design" and mentions order (calendar, leaderboard, stock prices), think TreeMap first.
Practice saying the TreeMap method names out loud: floor ≤, ceiling ≥, lower <, higher >. Bas itna yaad rakho — the name tells you the comparison.

09 · why & how

Questions you might be too shy to ask

If TreeMap exists, why learn to write a BST?

Because interviews test the ideas: why search is O(h), how delete works, why inorder is sorted. Those ideas power problems where you're handed a TreeNode (validate, kth smallest, LCA, successor) and can't use a TreeMap.

Is a BST the same as a heap?

No. A BST orders left < node < right (good for search and sorted order). A heap only promises parent ≤ children (good for repeatedly taking the minimum). A heap can't search for an arbitrary value faster than O(n).

Can I just say "O(log n)" for every BST problem?

No — say O(h). LeetCode's BSTs are not promised to be balanced. Insert 1, 2, 3, 4, 5 in that order and every value goes right: a chain with h = n − 1. So: "O(h) — O(log n) if balanced, O(n) if skewed." Only TreeMap / TreeSet guarantee O(log n), because they rebalance themselves.

What if my BST has duplicates?

Decide a rule (duplicates go right, or keep a count in the node) and apply it everywhere. With TreeMap, store counts: map.merge(x, 1, Integer::sum). Dhyan do: a TreeSet silently ignores a duplicate — add just returns false — so it can't count copies.

Why is the successor the right replacement when deleting a node with two children?

The successor is the smallest value bigger than the deleted one. So it's larger than everything on the left and smaller than everything else on the right — exactly the property the node's slot needs.

Validate BST: when I go left, why does high change but low stay the same?

Each node carries the range (low, high) that all its ancestors allow. The root gets (−∞, +∞) — the code writes "no limit" as null. Going left from 5 adds one new rule: "smaller than 5". So high = 5; the old low still applies. Going right adds "bigger than 5", so low = 5. Tree 5 → right 6 → left 3: at 3 the range is (5, 6), and 3 fails — even though 3 < 6 looks fine locally.

Kth smallest is inorder. What about kth largest?

Run inorder backwards: right → node → left. That visits values from largest to smallest, so the kth pop is the kth largest. Same iterative loop, just swap every left with right. Or, if you already know n, the kth largest is the (n − k + 1)th smallest.

How do I find the inorder successor without parent pointers?

Walk from the root. Each node bigger than p is a candidate; remember it and go left to look for a closer one. Each node ≤ p is useless; go right. When you fall off the tree, the last candidate is the answer. If p has a right subtree you will end at its leftmost node; if not, at the last ancestor where the path to p turned left.

Sorted array to BST: which middle do I pick when the length is even?

Either one. For [1, 2, 3, 4], root 2 or root 3 both give a height-balanced tree. mid = lo + (hi - lo) / 2 picks the left middle; lo + (hi - lo + 1) / 2 picks the right one. LeetCode accepts any height-balanced answer, so your tree may look different from the example and still pass.

BST Iterator: how is next() O(1) if one call can push many nodes?

Count over all the calls, not one. Every node is pushed exactly once and popped exactly once. So n calls to next() do about 2n stack operations in total — O(1) per call on average (amortized). One call may push h nodes, but then the next few calls push nothing. Memory stays O(h).

When should I pick TreeMap over HashMap?

When order matters: sorted iteration, smallest/largest key, or "nearest key to x". If you only need get/put/contains, HashMap's O(1) average wins.

How do AVL and red-black trees stay balanced?

After an insert or delete they check a local rule (AVL: subtree heights differ by ≤ 1; red-black: colour rules) and fix violations with rotations — O(1) pointer swaps that change the shape but keep the inorder order. You don't need to code them in interviews; know what they guarantee.

AVL or red-black — which is better?

AVL is more strictly balanced (height ≤ ~1.44 log₂ n), so lookups are slightly faster. Red-black allows a bit more imbalance (height ≤ 2 log₂(n+1)) and does fewer rotations on updates. Java's TreeMap, C++ std::map (in the major implementations) and the Linux kernel use red-black trees.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#700
Search in a Binary Search Tree
EasyGoogleMetaAmazonMicrosoftBloomberg
#701
Insert into a Binary Search Tree
MediumMicrosoftAmazonGoogleLinkedInBloomberg
#450
Delete Node in a BSTmust-do
MediumOracleUberByteDance / TikTokFlipkartAmazon+1
#98
Validate Binary Search Treemust-do
MediumBloombergMicrosoftAmazonMetaOracle+1
#230
Kth Smallest Element in a BSTmust-do
MediumUberOracleBloombergAmazonMicrosoft+1
#235
Lowest Common Ancestor of a Binary Search Treemust-do
MediumLinkedInMetaBloombergAmazonMicrosoft+1
#285
Inorder Successor in BSTmust-doLeetCode Premium
MediumMicrosoftMetaGoogleAmazon
#530
Minimum Absolute Difference in BST
EasyGoogleAmazon
#108
Convert Sorted Array to Binary Search Tree
EasyAirbnbAmazonMicrosoftAppleGoogle+1
#173
Binary Search Tree Iteratormust-do
MediumMetaLinkedInMicrosoftAmazonGoogle+1
#220
Contains Duplicate III
HardNetflixAirbnbMicrosoftBloombergAmazon+1
#729
My Calendar I
MediumUberIntuitByteDance / TikTokGoogleAmazon+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#94
Binary Tree Inorder Traversal
Easyin Traversals
The iterative inorder with a stack is the engine of Kth Smallest, BST Iterator and Validate — practise it until it's automatic.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A binary tree with one promise at every node: left subtree < node < right subtree. Inorder (left, node, right) reads the values sorted.
use it when
Sorted order or nearest-key questions on a changing set: floor/ceiling, kth smallest, successor, bookings. Handed a BST? Think inorder or a one-path walk.
template
One-path walk: while (cur != null) cur = x < cur.val ? cur.left : cur.right; — search, insert, LCA and successor all start here.
cost
Search/insert/delete/floor = O(h). Balanced: h ≈ log₂ n (20 levels for 10 lakh keys). Sorted inserts into a plain BST: h = n − 1. TreeMap guarantees O(log n).
trap
Checking only left.val < node.val < right.val misses grandchildren. Pass (low, high) bounds down — as null/long, never Integer.MIN_VALUE sentinels.
trap
Recursive insert/delete must re-link: root.left = deleteNode(root.left, key); Drop the assignment and the change is lost.
pro tip
Delete with two children: copy the in-order successor (leftmost of the right subtree), then delete it from the right subtree — it has no left child.
pro tip
Successor/ceiling: every node bigger than x is a candidate — remember it and go left. The last candidate wins. O(h), O(1) space.
pro tip
TreeMap/TreeSet are red-black BSTs: floorKey ≤, ceilingKey ≥, lowerKey <, higherKey >. All return null when nothing qualifies.

12 · recall

Flip, remember, repeat

card 1 / 14

recall

What exactly does the BST property promise?

tap or Space to flip ↻

Question 1: What exactly does the BST property promise?

13 · check yourself

Quick quiz

Is [5, 4, 6, null, null, 3, 7] a valid BST?
What does an inorder traversal of a BST produce?
You insert 1, 2, 3, 4, 5 into an empty plain BST. What is its height (edges)?
Deleting a node with two children: which value replaces it?
In [20, 10, 30, 5, 15], what is the inorder successor of 15?
TreeMap keys {10, 20, 30}. What is floorKey(25) and higherKey(30)?
Why is Java's TreeMap guaranteed O(log n) when a hand-written BST is not?
In BST Iterator, why is next() O(1) amortized even though one call may push h nodes?

0/0 correct · 8 left

14 · learn more