Home/Trees/Binary search tree
Search algorithmsCTRL K

Binary search tree

· insert, search and delete
/trees/binary-search-tree
NODES
1/ 12
in the tree
COMPARISONS
0
key against key
HEIGHT
1
levels, root included
OPERATION
insert
running now
KEY
24
being handled
comparingpathnew · successorbeing removed
12 keys · seed 7 · 65 steps
step 0 / 64
Keys12
binary_search_tree.ts
1
function insert(root: Node | null, key: number): Node {
2
  if (root === null) return { key, left: null, right: null };
3
  if (key < root.key) root.left = insert(root.left, key);
4
  else root.right = insert(root.right, key);
5
  return root;
6
}
7
function search(root: Node | null, key: number): Node | null {
8
  if (root === null || root.key === key) return root;
9
  return key < root.key ? search(root.left, key) : search(root.right, key);
10
}
11
function remove(root: Node | null, key: number): Node | null {
12
  if (root === null) return null;
13
  if (key < root.key) root.left = remove(root.left, key);
14
  else if (key > root.key) root.right = remove(root.right, key);
15
  else if (root.left === null) return root.right;
16
  else if (root.right === null) return root.left;
17
  else {
18
    const successor = minimum(root.right);
19
    root.key = successor.key;
20
    root.right = remove(root.right, successor.key);
21
  }
22
  return root;
23
}
CURRENT STEP
line 2

The tree is empty: 24 becomes the root.

// how it works

Understanding Binary search tree

BST · smaller keys left, larger keys right, all the way down
01

The idea

A binary search tree keeps one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. Insert and search both walk down from the root, turning left or right after one comparison per level, so the cost of every operation is the height of the tree.

Delete has three cases. A leaf is simply unlinked; a node with one child is replaced by that child; a node with two children takes the key of its in-order successor, the smallest key in its right subtree, and that successor, which has at most one child, is removed instead.

02

The four stages

1
comparekey against the current node
2
descendleft if smaller, right otherwise
3
attachan empty spot takes the new key
4
unlinkleaf, one child, or successor swap
03

Complexity

best
O(log n)balanced by luck
average
O(log n)random keys: about 2 log₂ n deep
worst
O(n)sorted input makes a linked list
space
O(n)one node per key
04

Versus its siblings

WORST HEIGHT · 1 000 000 KEYS
bst, random
60
bst, sorted
1M
avl
29
red-black
40
b-tree, order 128
3
a lookup costs one comparison per level
05

Pseudocode

INSERT(node, key)
  if node is null: return a new leaf with key
  if key < node.key: node.left ← INSERT(node.left, key) else node.right ← INSERT(node.right, key)
REMOVE(node, key)
  descend to the node holding key
  no left child: replace it by its right child (also covers a leaf)
  no right child: replace it by its left child
  two children: copy the successor's key into it, then REMOVE the successor from the right subtree
06

When to use

Ordered data with random arrivals: in-order traversal gives the keys sorted, predecessor and successor are cheap.
Teaching and prototypes; in production reach for a balanced variant or a hash map.
07

Pitfalls

Sorted or nearly sorted input degrades it to O(n) per operation. AVL and red-black trees fix that.
Deleting with the predecessor on one call and the successor on the next keeps the tree more even; always using one side skews it.
Duplicates need a rule (go right, or count them) or search becomes ambiguous.
08

History

Binary search trees appeared independently in several places around 1960; Windley, Booth and Colin, and Hibbard each published versions. Hibbard's 1962 paper gave the deletion algorithm shown here and the first analysis of random trees, showing the expected depth is logarithmic.

Back to Trees