Trees
Binary Search Tree Fundamentals
A binary search tree (BST) is a binary tree with an ordering invariant: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This property enables O(log n) search, insert, and delete when the tree is balanced. BSTs power Java’s TreeMap/TreeSet, C++’s std::set, and underpin database indexes.
01
Section One · Foundation
What is BST?
A BST enforces one simple rule: left < node < right. For every node, every value in its left subtree is strictly less, and every value in its right subtree is strictly greater. This invariant turns the tree into a sorted structure — an inorder traversal yields elements in sorted order, and searching is like binary search: at each node, go left if the target is smaller, right if larger, eliminating half the remaining tree each step.
The critical issue: a BST is only efficient when balanced.
Balanced BST
Height ≈ log n
AVL trees and Red-Black trees automatically rebalance after every insert/delete via rotations, keeping the height at O(log n) and guaranteeing O(log n) for all operations.
- AVL: strict balance (height diff ≤ 1)
- Red-Black: relaxed balance (faster inserts)
- Java
TreeMap= Red-Black tree
Unbalanced BST
Height ≈ n (worst case)
If you insert sorted data into a plain BST, it degenerates into a linked list. Every operation becomes O(n). This is why self-balancing variants exist.
- Insert [1,2,3,4,5] → a right-skewed chain
- Search becomes linear scan
- Never use a plain BST in production
Analogy: A dictionary (the book kind). To find a word, you open to the middle — if your word comes earlier alphabetically, you look in the left half; otherwise, the right half. Each step cuts the remaining pages in half. But if someone ripped out pages and glued them into a single long strip, you’d have to scan linearly — that’s an unbalanced BST.
Key Characteristics
Left < Node < Right invariant
▶
Inorder traversal yields sorted output
Binary search at each node
▶
O(log n) search when balanced — each step halves candidates
Insertion maintains the invariant
▶
New values always land at a leaf position
Deletion has three cases
▶
Leaf, one-child, two-child (replace with inorder successor)
No balancing → degenerates to linked list
▶
All operations become O(n) — self-balancing variants fix this
02
Section Two · Operations
Core Operations
Search
Finds a target value by comparing at each node and going left (smaller) or right (larger) — like binary search on a sorted array.
Pseudocode
function search(node, target):
if node is null:
return null // not found if target == node.val:
return node // found if target < node.val:
return search(node.left, target)
else:
return search(node.right, target)
// O(h) — O(log n) balanced, O(n) skewed
BST search is just binary search on a tree. At each node you eliminate an entire subtree. On a balanced BST with 1 million nodes, you find any value in ≤ 20 comparisons (log₂ 1,000,000 ≈ 20). The iterative version replaces recursion with a while loop — same logic, O(1) extra space.
Insert
Walks down the tree using the BST rule until it finds a null spot, then attaches the new node as a leaf.
Pseudocode
function insert(node, val):
if node is null:
return new Node(val) // attach here if val < node.val:
node.left = insert(node.left, val)
else:
node.right = insert(node.right, val)
return node // O(h)
New nodes always become leaves. The recursive approach is elegant: walk down, and on the way back up, reattach the subtree. This naturally handles the assignment
node.left = insert(node.left, val). The same pattern is used by delete — learn it once, apply everywhere.Delete
Removes a node while preserving the BST invariant — three cases: leaf, one child, two children.
Pseudocode
function delete(node, target):
if node is null: return null if target < node.val:
node.left = delete(node.left, target)
else if target > node.val:
node.right = delete(node.right, target)
else: // found the node if node.left is null: // case 1&2: 0 or 1 child return node.right
if node.right is null:
return node.left
// case 3: two children
successor = findMin(node.right)
node.val = successor.val // copy successor value
node.right = delete(node.right, successor.val)
return node // O(h)
Two-child deletion: replace with the inorder successor. The inorder successor is the smallest node in the right subtree (go right once, then left all the way). Copy its value into the node being deleted, then recursively delete the successor from the right subtree. This preserves the BST invariant because the successor is larger than everything in the left subtree and smaller than everything else in the right subtree.
Validate BST
Checks whether a binary tree satisfies the BST invariant by passing valid min/max bounds down each path.
Pseudocode
function isValidBST(node, min, max):
if node is null: return true if node.val <= min or node.val >= max:
return false return isValidBST(node.left, min, node.val) and isValidBST(node.right, node.val, max)
// initial call: isValidBST(root, -∞, +∞)
Don’t just check left < node < right — you need global bounds. A common mistake: checking only that
node.left.val < node.val. This misses cases where a deep-left node violates an ancestor’s constraint. The correct approach passes min and max bounds down the tree. Alternatively, do an inorder traversal and check that the sequence is strictly increasing. Common Mistake: Confusing “left child < node” with the full BST invariant. The rule is: every node in the left subtree is less, not just the immediate left child. A node at depth 5 must satisfy constraints from all its ancestors. Always validate with min/max bounds or a full inorder check.
03
Section Three · Visuals
Diagrams & Operations
BST Search — Finding Value 6
Binary search path: 8 → 3 → 6 — three comparisons
Insert Operation — Adding 5
Walk down using BST rule, attach as leaf: 8 → 3 → 6 → left of 6
Delete — Three Cases
Leaf deletion, one-child, and two-child (inorder successor replacement)
04
Section Four · Code
Java Quick Reference
Java’s TreeMap and TreeSet are self-balancing BSTs (Red-Black trees). For interviews, you’ll also need the manual recursive search/insert/delete.
Java — TreeMap (built-in BST)
import java.util.*;
TreeMap<Integer, String> map = new TreeMap<>();
map.put(8, "eight"); // O(log n)
map.put(3, "three");
map.put(10, "ten");
String v = map.get(3); // "three" — O(log n) boolean has = map.containsKey(8); // true
map.remove(10); // O(log n) // Sorted order iteration for (int key : map.keySet()) // 3, 8 (sorted!) System.out.println(key);
// Range queries — BST superpower
map.firstKey(); // 3 — smallest key, O(log n)
map.lastKey(); // 8 — largest key, O(log n)
map.floorKey(5); // 3 — largest ≤ 5
map.ceilingKey(5); // 8 — smallest ≥ 5
BST — Full Implementation
Java — BST from scratch
class BST {
static class Node {
int val; Node left, right;
Node(int v) { val = v; }
}
Node root;
// ── Search O(h) ─────────────────────── Node search(Node n, int target) {
if (n == null || n.val == target) return n;
return target < n.val ? search(n.left, target) : search(n.right, target);
}
// ── Insert O(h) ─────────────────────── Node insert(Node n, int val) {
if (n == null) return new Node(val);
if (val < n.val) n.left = insert(n.left, val);
else n.right = insert(n.right, val);
return n;
}
// ── Delete O(h) ─────────────────────── Node delete(Node n, int target) {
if (n == null) return null;
if (target < n.val) n.left = delete(n.left, target);
else if (target > n.val) n.right = delete(n.right, target);
else {
if (n.left == null) return n.right;
if (n.right == null) return n.left;
Node succ = findMin(n.right);
n.val = succ.val;
n.right = delete(n.right, succ.val);
}
return n;
}
Node findMin(Node n) { while (n.left != null) n = n.left; return n; }
// ── Validate BST O(n) ──────────────── boolean isValid(Node n, long min, long max) {
if (n == null) return true;
if (n.val <= min || n.val >= max) return false;
return isValid(n.left, min, n.val) && isValid(n.right, n.val, max);
}
// ── Inorder (sorted) O(n) ───────────── void inorder(Node n, List<Integer> res) {
if (n == null) return;
inorder(n.left, res);
res.add(n.val);
inorder(n.right, res);
}
// ── Kth Smallest O(h + k) ───────────── int count, result;
int kthSmallest(Node root, int k) {
count = k;
kthHelper(root);
return result;
}
void kthHelper(Node n) {
if (n == null) return;
kthHelper(n.left);
if (--count == 0) { result = n.val; return; }
kthHelper(n.right);
}
}
Python — BST from scratch
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def search(node, target): # O(h) if not node or node.val == target: return node
return search(node.left, target) if target < node.val else search(node.right, target)
def insert(node, val): # O(h) if not node: return TreeNode(val)
if val < node.val: node.left = insert(node.left, val)
else: node.right = insert(node.right, val)
return node
def delete(node, target): # O(h) if not node: return None if target < node.val: node.left = delete(node.left, target)
elif target > node.val: node.right = delete(node.right, target)
else:
if not node.left: return node.right
if not node.right: return node.left
succ = node.right
while succ.left: succ = succ.left
node.val = succ.val
node.right = delete(node.right, succ.val)
return node
def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if not node: return True if node.val <= lo or node.val >= hi: return False return is_valid_bst(node.left, lo, node.val) and is_valid_bst(node.right, node.val, hi)
def kth_smallest(root, k):
stack, cur = [], root
while stack or cur:
while cur:
stack.append(cur); cur = cur.left
cur = stack.pop()
k -= 1 if k == 0: return cur.val
cur = cur.right
JavaScript — BST class (ES6)
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val; this.left = left; this.right = right;
}
}
function search(node, target) {
if (!node || node.val === target) return node;
return target < node.val ? search(node.left, target) : search(node.right, target);
}
function insert(node, val) {
if (!node) return new TreeNode(val);
if (val < node.val) node.left = insert(node.left, val);
else node.right = insert(node.right, val);
return node;
}
function deleteNode(node, target) {
if (!node) return null;
if (target < node.val) node.left = deleteNode(node.left, target);
else if (target > node.val) node.right = deleteNode(node.right, target);
else {
if (!node.left) return node.right;
if (!node.right) return node.left;
let succ = node.right;
while (succ.left) succ = succ.left;
node.val = succ.val;
node.right = deleteNode(node.right, succ.val);
}
return node;
}
function isValidBST(node, lo = -Infinity, hi = Infinity) {
if (!node) return true;
if (node.val <= lo || node.val >= hi) return false;
return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}
C# — SortedDictionary (built-in) & manual BST
using System;
using System.Collections.Generic;
// Built-in sorted BST var map = new SortedDictionary<int, string>();
map[8] = "eight"; map[3] = "three"; map[10] = "ten";
foreach (var kv in map)
Console.WriteLine($"{kv.Key}: {kv.Value}"); // 3,8,10 sorted // Manual BST public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int v) { val = v; }
}
static TreeNode Insert(TreeNode n, int val) {
if (n == null) return new TreeNode(val);
if (val < n.val) n.left = Insert(n.left, val);
else n.right = Insert(n.right, val);
return n;
}
static bool IsValid(TreeNode n, long lo = long.MinValue, long hi = long.MaxValue) {
if (n == null) return true;
if (n.val <= lo || n.val >= hi) return false;
return IsValid(n.left, lo, n.val) && IsValid(n.right, n.val, hi);
}
05
Section Five · Complexity
Time & Space Complexity
| Operation | Balanced (AVL/RB) | Unbalanced (worst) | Space |
|---|---|---|---|
| Search | O(log n) | O(n) | O(h) recursive / O(1) iterative |
| Insert | O(log n) | O(n) | O(h) recursive |
| Delete | O(log n) | O(n) | O(h) recursive |
| Inorder traversal | O(n) | O(n) | O(h) stack |
| Find min / max | O(log n) | O(n) | O(1) iterative |
Why these complexities? Every BST operation walks a root-to-node path of length h. In a balanced tree, h = O(log n) because each level doubles the number of nodes. In the worst case (sorted insertion), h = n and the tree becomes a linked list. Self-balancing trees (AVL, Red-Black) maintain h = O(log n) via rotations after every mutation, guaranteeing logarithmic performance for all operations.
Space Complexity Note
A BST of n nodes uses O(n) space for the nodes. Recursive operations use O(h) call-stack space. For balanced trees h = O(log n); for skewed trees h = O(n). Iterative search uses O(1) auxiliary space. Self-balancing trees add a small constant per node (colour bit for Red-Black, balance factor for AVL) but this doesn’t change the asymptotic space.
06
Section Six · Decision Guide
When to Use BST
Use This When
- You need sorted-order operations — find the kth smallest, iterate in sorted order, find the predecessor/successor of a value.
- Range queries — “all keys between 10 and 50”, floor/ceiling lookups. TreeMap’s
subMap,floorKey,ceilingKeyrely on BST structure. - Dynamic sorted data — when elements are frequently inserted/deleted and you still need sorted access. Arrays need O(n) shifts; BSTs do it in O(log n).
Avoid When
- You only need key existence / lookup — HashMap is O(1) average vs. BST’s O(log n). If you don’t need ordering, a hash map is always faster.
- Data is static and sorted — binary search on a sorted array gives O(log n) search with better cache performance and no pointer overhead.
Comparison vs Alternatives
| Structure | Search | Insert | Ordered? | Best For |
|---|---|---|---|---|
| BST (balanced) ← this one | O(log n) | O(log n) | Yes | Sorted data, range queries, kth element |
| HashMap | O(1) avg | O(1) avg | No | Pure lookup, frequency counting |
| Sorted Array | O(log n) | O(n) shift | Yes | Static data, binary search |
07
Section Seven · Interview Practice
LeetCode Problems
BST interview problems test two things: exploiting the sorted invariant (validate BST, kth smallest, inorder successor) and structural mutations (insert, delete, convert sorted array to BST). The key insight is always the same: inorder traversal = sorted order, and you can prune half the tree at each step.
- Easy Search in a BST — Go left if target < node, right if target > node, return when equal — O(h) recursive or iterative.
- Medium Validate Binary Search Tree — Pass min/max bounds down recursively, or do an inorder traversal and check strictly increasing.
- Medium Kth Smallest Element in a BST — Inorder traversal stopping at the kth node — O(h + k). Iterative stack version is cleaner.
- Medium Delete Node in a BST — Find the node, handle three cases: leaf, one child, two children (swap with inorder successor).
- Hard Recover Binary Search Tree — Two nodes are swapped. Do an inorder traversal; find two violations in the sorted sequence and swap them back.
Interview Pattern: When a problem involves a BST, always think “inorder = sorted.” If you need the kth smallest, predecessor, or need to validate the tree, an inorder traversal (iterative with a stack or Morris traversal for O(1) space) is usually the cleanest approach. For search/insert/delete, use the recursive “reassign on the way back up” pattern.