Data structure 10 of 12

Binary search trees and sorted maps

A binary search tree is a binary tree with one rule: everything on the left is smaller, everything on the right is bigger. That rule lets you throw away half of what's left at every step, like guessing a number with "higher" and "lower".

A 2-minute conversation: Sam asks, Priya explains

0:00 / 2:15

Follow along on the page Pause on “your turn” questions

Sam Binary search trees. What makes them special?
Priya One rule: everything on the left is smaller, everything on the right is bigger. That lets you throw away half of what's left at every step, like the higher-or-lower guessing game.
Priya "I'm thinking of a number between one and a hundred." Each guess rules out half, so seven guesses are always enough. A search tree builds that game into the shape of the data.
Sam Is it always fast?
Priya Only when it's balanced. Search, insert and delete follow one path, so they cost the height. Balanced, that's about log n. Insert one, two, three, four in order and you get a chain, as slow as a list.
Sam And sorted maps?
Priya Java's TreeMap and TreeSet are self-balancing search trees. They rotate nodes after inserts so the height stays about log n.
Sam Costs?
Priya Balanced: search, insert, delete, smallest, largest and next bigger are all logarithmic. And an in-order traversal lists every value in sorted order.
Priya Your turn. You need the smallest key bigger than x, many times, while keys are added. Hash map or sorted map?
Priya A sorted map. A hash map has no order at all.
Sam Python?
Priya No built-in balanced tree. Use bisect on a sorted list for small inputs, or the sortedcontainers package where allowed. Java has TreeMap, with firstKey, higherKey and floorKey.
Sam The players?
Priya Search: equal is found, smaller goes left, bigger goes right. Insert: walk down as if searching and put the new value where the search fell off. And in-order traversal: left, node, right, which comes out sorted.
Sam Memory hook?
Priya Higher or lower. Left is less, right is more, in-order is sorted.
Sam Problems?
Priya Search in a BST, the recursive version. And range sum of a BST, which skips a whole subtree when the ordering rule says it can't contain values in range.
Sam Mistakes?
Priya Validating by checking only the children, when every descendant counts. Assuming the tree is balanced. Using a search tree when a hash map would do. And forgetting Python has no TreeMap.
Sam Next?
Priya Lesson eleven, graphs.

1. What it is

The number-guessing game: "I'm thinking of a number between 1 and 100." Each guess, "higher" or "lower", rules out half of what's left, so seven guesses are always enough. A binary search tree builds that game into the shape of the data: at every node, go left for smaller, right for bigger.

A binary search tree (BST) is a binary tree where, for every node, all values in the left subtree are smaller and all values in the right subtree are bigger. (Problems say how duplicates are handled; often there are none.)

Search, insert, delete follow one path from the root: O(h), where h is the height.
Balanced (h about log n): very fast. Unbalanced (inserting 1, 2, 3, … makes a chain): h = n, as slow as a list.
In-order traversal (left, node, right) visits the values in sorted order.
Sorted maps and sets in standard libraries (Java's TreeMap) are self-balancing BSTs: always O(log n).

2. How it sits in memory

Searching compares with the current node and goes one way; the other subtree is never looked at. Each step down halves the candidates in a balanced tree.

The same values can make very different trees, depending on insertion order. Balanced trees keep searches short; self-balancing trees (red-black, AVL) rotate nodes after inserts so the height stays about log n.

3. Operations and what they cost

Operation	Balanced BST	Chain-shaped BST	Sorted list (with binary search)
Search	`O(log n)`	`O(n)`	`O(log n)`
Insert, delete	`O(log n)`	`O(n)`	`O(n)` (shifting)
Smallest, largest	`O(log n)`	`O(n)`	`O(1)`
All values in order	`O(n)` in-order	`O(n)`	`O(n)`
Next bigger than x	`O(log n)`	`O(n)`	`O(log n)`

Hash map or sorted map?A hash map is faster for plain lookups (O(1)). Choose a sorted structure when you need order: the smallest key, the next key after x, or keys in a range.

4. In Python, TypeScript and Java

Python has no built-in balanced tree; use bisect on a sorted list for small inputs (insert is O(n)), or the third-party sortedcontainers package where allowed. Java's TreeMap and TreeSet are red-black trees.

import bisect
    nums = [2, 5, 9]
    bisect.insort(nums, 7)          # [2, 5, 7, 9], keeps it sorted (O(n) insert)
    i = bisect.bisect_left(nums, 6) # 2: where 6 would go
    next_bigger = nums[i]           # 7
    # from sortedcontainers import SortedList   # O(log n) inserts, if the judge allows it

// No built-in sorted tree in JavaScript. For small inputs, keep a sorted array
    // and binary-search it:
    function lowerBound(a: number[], x: number): number {
      let lo = 0, hi = a.length;
      while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; }
      return lo;
    }
    const nums = [2, 5, 9];
    nums.splice(lowerBound(nums, 7), 0, 7);   // [2, 5, 7, 9]

TreeMap<Integer, String> m = new TreeMap<>();
    m.put(5, "five"); m.put(2, "two"); m.put(9, "nine");
    int smallest = m.firstKey();             // 2
    Integer next = m.higherKey(5);           // 9: the next key above 5
    Integer atMost = m.floorKey(6);          // 5: the largest key ≤ 6
    SortedMap<Integer, String> range = m.subMap(2, 9);   // keys 2 ≤ k < 9
    TreeSet<Integer> s = new TreeSet<>(List.of(5, 2, 9));

5. Core operations, step by step

Three operations, each following one path from the root.

A · Search

What it doesCompares the target with the node: equal means found; smaller goes left; bigger goes right.

Picture itHigher or lower: each answer rules out a whole side.

CostO(h): one node per level.

The code. A loop is enough: no recursion needed.

def search(node, target):
    while node:
        if target == node.val:
            return True
        if target < node.val:
            node = node.left
        else:
            node = node.right
    return False

function search(node: TreeNode | null, target: number): boolean {
  while (node) {
    if (target === node.val) {
      return true;
    }
    if (target < node.val) {
      node = node.left;
    } else {
      node = node.right;
    }
  }
  return false;
}

static boolean search(TreeNode node, int target) {
    while (node != null) {
        if (target == node.val) {
            return true;
        }
        if (target < node.val) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return false;
}

Line by line.

Line	What it does	Why
`if target < node.val: node = node.left`	Smaller: everything we want is on the left.	The whole right subtree is skipped.
`return False`	Fell off the tree.	The target would have been on this path if it existed.

Watch it run. Search for 6, then picture 7, in the tree built from 8, 3, 10, 1, 6, 14, 4.

Watch out for:

Searching both subtrees. That's O(n) and ignores the ordering rule.

B · Insert

What it doesWalks down as if searching; the new value becomes a leaf where the search fell off.

Picture itPlay higher-or-lower until there's no node to compare with; that empty spot is where the new value lives.

CostO(h).

The code. The recursive form returns the (possibly new) subtree root, so the parent's link is updated for free.

def insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

function insert(node: TreeNode | null, val: number): TreeNode {
  if (node === null) {
    return new TreeNode(val);
  }
  if (val < node.val) {
    node.left = insert(node.left, val);
  } else {
    node.right = insert(node.right, val);
  }
  return node;
}
function insertAll(vals: number[]): TreeNode | null { let root: TreeNode | null = null; for (const v of vals) root = insert(root, v); return root; }

static TreeNode insert(TreeNode node, int val) {
    if (node == null) {
        return new TreeNode(val);
    }
    if (val < node.val) {
        node.left = insert(node.left, val);
    } else {
        node.right = insert(node.right, val);
    }
    return node;
}
static TreeNode insertAll(int... vals) { TreeNode root = null; for (int v : vals) root = insert(root, v); return root; }

Line by line.

Line	What it does	Why
`if node is None: return TreeNode(val)`	Found the empty spot: make the leaf.	The caller stores it as its left or right child.
`node.left = insert(node.left, val)`	Insert into the left subtree and re-attach it.	Re-attaching every level is harmless and avoids special cases.
`return node`	This subtree's root is unchanged.

Watch it run. Insert 7 into the tree built from 8, 3, 10, 6.

Watch out for:

Inserting sorted input. 1, 2, 3, 4 … builds a chain: every operation becomes O(n). Self-balancing trees fix this.

C · In-order traversal gives sorted order

What it doesVisits the left subtree, then the node, then the right subtree.

Picture itEverything smaller is on your left, so visiting the left side first means meeting values smallest first.

CostO(n).

The code. A plain recursive traversal; the BST rule makes the output sorted.

def in_order(node, out):
    if node is None:
        return out
    in_order(node.left, out)
    out.append(node.val)
    in_order(node.right, out)
    return out

def insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

function inOrder(node: TreeNode | null, out: number[]): number[] {
  if (node === null) {
    return out;
  }
  inOrder(node.left, out);
  out.push(node.val);
  inOrder(node.right, out);
  return out;
}
function insert(node: TreeNode | null, val: number): TreeNode { 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; }

static List<Integer> inOrder(TreeNode node, List<Integer> out) {
    if (node == null) {
        return out;
    }
    inOrder(node.left, out);
    out.add(node.val);
    inOrder(node.right, out);
    return out;
}
static TreeNode insert(TreeNode node, int val) { if (node == null) return new TreeNode(val); if (val < node.val) node.left = insert(node.left, val); else node.right = insert(node.right, val); return node; }

Line by line.

Line	What it does	Why
`in_order(node.left, out)`	Everything smaller first.	The whole left subtree is smaller than this node.
`out.append(node.val)`	Then the node itself.	Moving this line before or after the calls gives preorder or postorder instead.

Watch it run. The tree built from 8, 3, 10, 1, 6, 14, 4.

Watch out for:

Expecting sorted output from preorder. Only in-order (left, node, right) is sorted for a BST.

6. How to remember it

Memory hook: "Higher or lower"At every node: smaller, go left; bigger, go right; equal, found. One path down, half the tree gone each step, as long as the tree stays bushy.

Picture

A signpost at every fork: "smaller ←, bigger →".

Chant

"Left is less, right is more, in-order is sorted."

Key rule

Speed depends on the height. Sorted input makes a chain; balanced trees keep it log n.

7. Problems solved with it

Two easy problems that use the ordering rule to skip work.

LC 700 · Search in a Binary Search Tree

The problemReturn the subtree rooted at the node whose value is val, or null.

What it doesOperation A, returning the node instead of true.

CostO(h).

The code. Recursive this time, to compare with the loop.

def search_bst(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        return search_bst(node.left, val)
    return search_bst(node.right, val)

function searchBST(node: TreeNode | null, val: number): TreeNode | null {
  if (node === null || node.val === val) {
    return node;
  }
  if (val < node.val) {
    return searchBST(node.left, val);
  }
  return searchBST(node.right, val);
}

static TreeNode searchBST(TreeNode node, int val) {
    if (node == null || node.val == val) {
        return node;
    }
    if (val < node.val) {
        return searchBST(node.left, val);
    }
    return searchBST(node.right, val);
}

Line by line.

Line	What it does	Why
`if node is None or node.val == val`	Either fell off or found it.	Both cases return node (None or the match).

Watch it run. Search for 2 in the tree built from 4, 2, 7, 1, 3.

Watch out for:

Recursing into both children. One side is enough.

LC 938 · Range Sum of BST

The problemReturn the sum of values in the BST that lie between low and high inclusive.

What it doesSkips a whole subtree when the ordering rule says it can't contain values in range.

CostO(n) worst case, often much less.

The code. Too small? Only the right side can help. Too big? Only the left.

def range_sum(node, low, high):
    if node is None:
        return 0
    if node.val < low:
        return range_sum(node.right, low, high)
    if node.val > high:
        return range_sum(node.left, low, high)
    return node.val + range_sum(node.left, low, high) + range_sum(node.right, low, high)

function rangeSum(node: TreeNode | null, low: number, high: number): number {
  if (node === null) {
    return 0;
  }
  if (node.val < low) {
    return rangeSum(node.right, low, high);
  }
  if (node.val > high) {
    return rangeSum(node.left, low, high);
  }
  return node.val + rangeSum(node.left, low, high) + rangeSum(node.right, low, high);
}

static int rangeSum(TreeNode node, int low, int high) {
    if (node == null) {
        return 0;
    }
    if (node.val < low) {
        return rangeSum(node.right, low, high);
    }
    if (node.val > high) {
        return rangeSum(node.left, low, high);
    }
    return node.val + rangeSum(node.left, low, high) + rangeSum(node.right, low, high);
}

Line by line.

Line	What it does	Why
`if node.val < low: return range_sum(node.right, ...)`	This node and its whole left side are too small.	Skipping the left subtree is the BST rule at work.
`return node.val + ...`	In range: count it and search both sides.

Watch it run. Values between 7 and 15 in the tree built from 10, 5, 15, 3, 7, 18.

Watch out for:

Visiting every node. Correct, but throws away the speed-up the ordering gives.

More practice, solved on the pattern pages

#	Problem	Level	Where
108	Convert Sorted Array to Binary Search Tree	Easy	Solved step by step on 10 · Binary Tree Traversal
530	Minimum Absolute Difference in BST	Easy	Solved step by step on 10 · Binary Tree Traversal
98	Validate Binary Search Tree	Medium	Solved step by step on 10 · Binary Tree Traversal
230	Kth Smallest Element in a BST	Medium	Solved step by step on 10 · Binary Tree Traversal
701	Insert into a Binary Search Tree	Medium	Solved step by step on 10 · Binary Tree Traversal
235	Lowest Common Ancestor of a BST	Medium	Solved step by step on 10 · Binary Tree Traversal

8. Common mistakes

Checking only the childrenA BST needs every left descendant smaller, not just the left child. Validating means passing allowed ranges down (LC 98).

Assuming it's balancedA plain BST built from sorted input is a chain: O(n) per search. Say so in an interview, and mention self-balancing trees.

Reaching for a BST when a hash map will doIf you never need order, a hash map's O(1) beats O(log n).

Python has no TreeMapUse bisect on a sorted list (O(n) inserts), a heap if you only need the smallest, or sortedcontainers if allowed.

9. Self-check quiz

Searching for 4; the current node holds 8. What next?

Everything smaller than 8 is in the left subtree.

Which traversal of a BST lists the values in sorted order?

Left (smaller), node, right (bigger).

You insert 1, 2, 3, 4, 5 into an empty BST. What do you get?

Each value is bigger than all before it, so it always goes right.

You need the smallest key greater than x, many times. Hash map or sorted map?

Hash maps have no order; a sorted map answers in O(log n).

10. Where it shows up next

10 · Binary Tree Traversal: validating BSTs, the k-th smallest, and lowest common ancestors.
09 · Modified Binary Search: the same halving idea on a sorted array.
24 · Segment Tree & Fenwick: trees built for range questions.

Next structure: 11 · Graphs: nodes and edges with no root and no rules about direction.