Binary Search Tree, step by step.

// how binary search trees work

How a binary search tree works

What is a binary search tree?

A binary search tree (BST) is a binary tree whose keys are kept in order: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. A node can hold data along with its key.

The rule covers whole subtrees, not just the two children. In the example tree drawn below, 35 sits in the root's left subtree, below 20 and 27. A 40 placed by hand as the right child of 35 would be larger than 35, 27 and 20, but not smaller than the root 38.

This page and the app use distinct keys: a key already in the tree is not inserted again.

Binary search tree vs binary tree

In a plain binary tree a key can be anywhere, so a search may visit every node: O(n). In a binary search tree each comparison rules out a subtree, so a search follows one path from the root: O(h), where h is the tree's height.

Sorted order: the keys read left to right

Read from left to right, the keys of a binary search tree are in ascending order, as the figure below shows for the fifteen-key example tree. Visiting the nodes in this order is called an in-order traversal.

Binary search tree terms: root, leaf, depth, height, level

The root is the top node, here 38. A leaf has no children. An edge joins a parent to a child, and a subtree is a node with all its descendants.

This page counts edges, as the app does. The depth of a node is the number of edges from the root to it, and nodes of equal depth form a level, numbered from 0 at the root. The height of a node is the number of edges on the longest path down to a leaf: a leaf has height 0, an empty tree −1. In the example tree, 43 has depth 1 and height 2, and the tree has height 3.

Searching a binary search tree

A search starts at the root. On a match it stops; a smaller key goes left, a larger one right; an empty link means the key is absent. Looking for 35: 35 < 38, go left; 35 > 20, go right; 35 > 27, go right to 35. Each animation below begins with this walk.

Binary search tree insertion

Insertion searches for the new key and attaches it where the search ends, as the left or right child of the last node visited. The new node is always a leaf, so the insertion order decides the tree's shape.

Here 42 is inserted into the example tree without 22, 35 and 39. 42 > 38, go right to 43; 42 < 43, go left to 41; 42 > 41, and 41 has no right child. 42 becomes the right child of 41. Step through it below.

Insert node 42

All steps as text

1. To insert 42, start at the root: 42 > 38, so go right.
2. 42 < 43, so go left.
3. 42 > 41, so go right.
4. 41 has no right child, so this is where 42 goes: the right child of 41.
5. When adding a new node to the binary search tree, it becomes either the left or right child of an existing node, depending on how its key compares to the keys in the tree.

Binary search tree deletion: the three cases

Deletion first searches for the key. What follows depends on the node's children.

Case	Node to delete	What takes its place
1	leaf	nothing: the link to it becomes empty
2	one child	the child, with its subtree
3	two children	the in-order successor, the smallest key in the right subtree

Case 1: deleting a leaf

The parent's link to the leaf is set to empty: null in Java, nullptr in C++, None in Python. If the leaf is the root, the tree becomes empty.

Here 22 is deleted from the fifteen-key example tree. 22 < 38, go left; 22 > 20, go right; 22 < 27, go left to 22. It is a leaf, so 27 keeps only its right child, 35. Step through it below.

Case 1: Delete node 22

All steps as text

1. To delete 22, first find it. Start at the root: 22 < 38, so go left.
2. 22 > 20, so go right.
3. 22 < 27, so go left.
4. Found 22. It is a leaf: it has no children.
5. In the case of a leaf node, deletion involves setting the corresponding left or right child link of the parent node to null (None in Python, nullptr in C++).

Case 2: deleting a node with one child

The child is linked to the deleted node's parent in its place and brings its whole subtree along. If the node is the root, its child becomes the new root.

Here the tree has no 1, so 5 has one child, 7, on its right. 5 < 38, go left; 5 < 20, go left to 5. 5 is removed, and 7 takes its place as the left child of 20. Step through it below.

Case 2: Delete node 5

All steps as text

1. To delete 5, first find it. Start at the root: 5 < 38, so go left.
2. 5 < 20, so go left.
3. Found 5. It has one child, 7.
4. When deleting a node with one child in the binary search tree, the child takes its place by linking to the parent of the deleted node, provided the parent is not null (None in Python, nullptr in C++).

Case 3: deleting a node with two children, the in-order successor

The node is replaced by its in-order successor, the smallest key in its right subtree. It has no left child but may have a right child.

The successor moves into the node's place and adopts its left subtree. If the successor is the node's own right child, it keeps its right subtree. Otherwise it also adopts the node's right subtree, and its own right child, if it has one, takes the successor's old place as the left child of the successor's parent.

Here the root 38 is deleted from the example tree without 39. The successor search goes right to 43, then left to 41, which has no left child: 41 is the successor. 41 takes the root's place, with 20 and 43 as its children, and its right child 42 becomes the left child of 43. Step through it below.

Case 3: Delete node 38

All steps as text

1. To delete 38, first find it: 38 is the root, with two children, 20 and 43.
2. Its successor is the smallest key in its right subtree. Go right to 43.
3. Go left to 41. It has no left child, so 41 is the successor.
4. When a node with two children is deleted from the binary search tree, it is replaced by its successor, the smallest node in its right subtree. If this successor has its own child, then that child takes the successor's place.

In-order successor vs predecessor

Some texts use the in-order predecessor instead, the largest key in the left subtree; for 38 above it is 35. This page and the app use the successor. Some implementations copy the successor's key into the node and then delete the successor, instead of moving the node as the animation does. The result is the same.

Height of a binary search tree

Every level of the example tree is full, and each holds twice as many nodes as the one above.

A tree with all levels full is called perfect. With height h it has n = 2^{h + 1} − 1 nodes, here 2⁴ − 1 = 15, so h = log₂(n + 1) − 1. No tree of height h holds more, so n keys need a height of at least log₂(n + 1) − 1. Counting height in nodes instead gives n = 2^h − 1.

Binary search tree time complexity

Search, insertion and deletion each follow one path down from the root, so each takes O(h) time. The height is O(log n) in a balanced tree, and is expected to be O(log n) when keys are inserted in random order, but it can reach n − 1.

Measure	Balanced	Worst case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Height	O(log n)	n − 1

Degenerate binary search tree: sorted input makes a chain

Inserted in ascending order, the keys 10, 20, 30, 40, 50, 60 and 70 each become the right child of the one before: a degenerate tree, in which every parent has one child. It is a chain seven levels tall, of height 6, like a linked list. The same keys form a B-tree of two levels on the B-tree page and an AVL tree of three levels on the AVL page.

Balanced and self-balancing binary search trees

A tree is called balanced when its height stays close to the minimum, O(log n). A common strict form is that at every node the two subtree heights differ by at most one.

A self-balancing tree repairs its shape after each insertion and deletion. An AVL tree keeps the strict rule, with rotations. A red-black tree keeps colour rules that hold its longest path to at most twice its shortest, with recolouring and rotations. A B-tree is not binary: it keeps several keys per node and all leaves at one depth. All three guarantee O(log n) operations.

Where binary search trees are used

• Ordered maps and sets: Java's TreeMap and C++ std::map are balanced binary search trees, usually red-black trees.
• Order queries: minimum, maximum, the nearest key below or above a value, and all keys in a range. A hash table finds a key in O(1) on average but keeps no order. A min-heap finds its minimum in O(1) but any other key only in O(n).