A binary search tree (BST) is a binary tree that keeps its keys in order: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. That order lets a search, an insertion or a deletion follow one path down from the root. This page explains how it works, with step-by-step animations of insertion and all three deletion cases from the VisiGrab app.
// how binary search trees work
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.
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.
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 inorder traversal.
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.
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.
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.
In the player, 42 is inserted into the example tree without 22, 35 and 39: the search passes 38, 43 and 41, and 42 becomes the right child of 41.
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 |
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.
In the player, the leaf 22 is deleted from the fifteen-key example tree, and its parent 27 keeps only its right child, 35.
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.
In the player, the tree has no 1, so 5 has one child, 7. 5 is removed, and 7 takes its place as the left child of 20.
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.
In the player, the root 38 is deleted from the example tree without 39. Its successor, 41, takes the root's place, and 41's right child, 42, becomes the left child of 43.
O(h), where h is the height of the tree: a search follows one path down from the root. That is O(log n) in a balanced tree, and on average when keys arrive in random order, but O(n) in the worst case, when sorted input makes the tree a chain.
Replace it with its in-order successor, the smallest key in its right subtree: go right once, then left as far as possible. The successor has no left child, so removing it from its old place is case 1 or 2: it is a leaf or has one child. The fourth player deletes the root 38 this way, with 41 as its successor.
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.
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 = 2h + 1 − 1 nodes, here 24 − 1 = 15, so h = log2(n + 1) − 1. No tree of height h holds more, so n keys need a height of at least log2(n + 1) − 1. Counting height in nodes instead gives n = 2h − 1.
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 |
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.
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 color rules that hold its longest path to at most twice its shortest, with recoloring 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.
TreeMap and C++ std::map are balanced binary search trees, usually red-black trees.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). For words, a trie keeps all words with the same prefix under one node.The full source code is on GitHub, in Python, Java and C++.
// in the app
In VisiGrab you build the tree yourself, and every change plays out step by step.
Insert any key with “+”, tap a node to delete it, or start from a random tree. Every insert and delete is kept in a list.
Step through every insertion and deletion, and step back through them.
Pre-order, in-order, post-order and breadth-first traversal, each a topic of its own.
Tree terms, height and depth, the kinds of binary trees, insertion and deletion, all illustrated.
A complete binary search tree implementation, explained part by part.
Check what you have learned before moving on.
// build your own
Download VisiGrab and step through every insertion and deletion yourself.
The binary search tree is one of 30+ topics. See them all