Binary Search Tree

Is 16 in here? A list checks the keys one by one; a binary search tree answers in a handful of comparisons, about 20 for a million keys if the tree is balanced.

★ Lecture: tree_BST · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

2Binary Search & Search on the AnswerSearching a BST is binary search frozen into the shape of a tree.5Trees: Concepts, Properties, TraversalsAn in-order traversal of a BST lists its keys in sorted order.

Leads to→

5Balanced Trees & set / mapA BST decays to O(n) when it grows into a chain; balancing keeps h = O(log n).

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01Smaller to the left, bigger to the right

A binary search tree (BST) is a binary tree in which, for every vertex:

every key in its left subtree is smaller than its key,
every key in its right subtree is bigger,
and both subtrees are binary search trees themselves.

Keys only need to be comparable: numbers, strings, dates. The lecture’s node has the pointers left, right and parent and the key value; depending on the task you can drop parent or add more fields.

Look at 17 in the figure: 16 hangs to its left and 19 to its right, and the whole subtree of 17 still sits inside the “< 20” region. Thanks to this rule, every operation in this lesson walks one path from the root downward, so it costs O(h), where h is the height of the tree.

The 12-key tree of the lecture. The rule holds at every vertex, not only at the root.

02Search and insert

Search starts at the root. If the key you want is bigger than the current vertex, go right; if smaller, go left; stop when you find it or fall off the tree (a NULL link means “not here”). Searching 16: 16 < 20, left; 16 > 14, right; 16 < 17, left; found. Four comparisons, one per level.

Insert is the same walk. To insert 35: 35 > 20, right; 35 > 32, right; 35 < 38, left, and 38 has no left child, so 35 becomes 38.left. A new key is always inserted as a leaf, exactly where a later search will look for it.

The lecture writes both recursively. The neat trick in insert is that it returns the root of the subtree, so the call node->left = insert(node->left, key) relinks the tree by itself, and an empty spot simply becomes newNode(key). A key that is already present is not inserted a second time.

search(16) and insert(35) from the lecture: one comparison per level.

03Inorder, minimum, maximum and neighbours

Run INORDER on a BST and the keys come out sorted: 9, 11, 14, 16, 17, 19, 20, 27, 30, 32, 38, 47. It visits the left subtree (all smaller), then the vertex, then the right subtree (all bigger). Insert keys in any order, print them with inorder, and you have sorted them.

The sorted view explains four more operations:

minimum: from the root keep going left until there is no left child (9);
maximum: keep going right (47);
the predecessor of a key is the maximum of its left subtree (for 20 that is 19);
the successor is the minimum of its right subtree (for 20 that is 27).

So findMin() and findMax() on a subtree give both neighbours. If that subtree is empty, the neighbour is one of the ancestors, and that is what the parent pointer is for. All four operations walk one path: O(h).

Drop every node straight down: you get the keys in sorted order.

04Delete: three cases

A delete must keep the BST rule. The lecture splits it into three cases:

a) a leaf: clear the pointer in its parent. Deleting 19 means 17.right = NULL.
b) one child: the child takes the deleted vertex’s place under its parent. Deleting 27 makes its child 30 the left child of 32; the whole subtree moves up a level and stays sorted.
c) two children: pulling a child up could break the rule, so replace the key by its successor (one step right, then left to the end) or by its predecessor. Deleting 14: its successor is 16 (right to 17, then left to 16), so 16 takes 14’s place and its old leaf is removed as in case a. The predecessor 11 would work just as well. In general the successor never has a left child, so removing it from its old spot is always case a or b.

The lecture’s deleteNode handles all three recursively: no left child → return the right one (this covers leaves); no right child → return the left one; otherwise copy the successor’s key and delete the successor from the right subtree.

The lecture’s three examples: delete 19, delete 27, delete 14.

05The cost O(h) and order statistics

Every operation so far walks one path from the root: O(h). With keys in random order h stays a small multiple of log n. With sorted keys each new key hangs to the right of the last one and the tree degenerates into a chain, h = n. Balanced trees (next lesson) fix that.

The lecture ends with a bonus, order statistics. Store in every node the size of its subtree and update it on every insert and delete. To find the k-th smallest key, let r = left.size + 1, the rank of the current vertex:

k == r → this vertex is the answer;
k < r → look for the k-th key in the left subtree;
k > r → look for the (k − r)-th key in the right subtree.

The 8th smallest: at 20, r = 7 < 8, go right with k = 1; at 32, r = 3, go left; at 27, r = 1 = k. The answer is 27, in O(h).

Subtree sizes under each node; the walk 20 → 32 → 27 finds the 8th smallest key.

The lecture's C++C++

The full program from slide 9 with the search function from slide 5 added: insert and search walk down the tree the same way, comparing with the key and turning left or right, and inorder prints the keys sorted.

#include <bits/stdc++.h>
using namespace std;
struct node { int key; struct node *left, *right; };
struct node* newNode(int item){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void inorder(struct node* root){
    if (root != NULL) {
        inorder(root->left);
        cout<<root->key<<" ";
        inorder(root->right);
    }
}
struct node* insert(struct node* node, int key){
    if (node == NULL) return newNode(key);
    if (key < node->key) node->left = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    return node;
}
//ძებნა BST-ში მოცემული ხისა და მოცემული რიცხვისათვის
struct node* search(struct node* root, int key) {
    // საბაზო შემთხვევა: სათავე null-ია ან საძებნი რიცხვი სათავეშია
    if (root == NULL || root->key == key) return root;
    // საძებნი რიცხვი სათავის მნიშვნელობაზე მეტია
    if (root->key < key) return search(root->right, key);
    // საძებნი რიცხვი სათავის მნიშვნელობაზე ნაკლებია
    return search(root->left, key);
}
int main() {
    struct node* root = NULL;
    root = insert(root, 100); insert(root, 50); insert(root, 150);
    insert(root, 25); insert(root, 75); insert(root, 125); insert(root, 175);
    inorder(root);
}

Cost at a glance

Search / insert / deleteO(h)

Min / max / predecessor / successorO(h)

Sorted output (inorder)O(n)

Height h: balanced … chainlog n … n

Remember

Left < node < right at every vertex, so search, insert, minimum and maximum each walk a single path: O(h).
Inorder lists a BST in sorted order; the predecessor and successor are a key’s neighbours in that list.
Delete has three cases (a leaf, one child, two children), and the case with two children borrows the successor.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Follow the comparison path: every step throws away a whole subtree. Then enter your own keys and delete the root to watch the successor move up.

Interactive visualizerfocus here, then space ← →

Binary search tree

comparison pathfound / insertedcurrent

SEARCH 16: start at the root. Each comparison discards a whole subtree. This is binary search, frozen into pointers.

Pseudocode

 1 search(x): start at root 2   if x == node.key: found 3   if x <  node.key: go left 4   if x >  node.key: go right 5 insert(x): search for x … 6   … attach x at the first null link 7 findMin(): keep going left 8 findMax(): keep going right 9 delete(x), x is a leaf:10   null the pointer in x’s parent11 delete(x), x has one child:12   the child takes x’s place under x’s parent13 delete(x), x has two children:14   successor s = min of right subtree; s replaces x

1 / 1

Check

Three questions. Pick an answer to see why.

Insert 50, 30, 70, 20, 40 into an empty BST, then insert 35. Where does 35 end up?

You delete a vertex with two children by replacing it with its successor. Why is removing the successor from its old place easy?

Keys 1, 2, 3, …, 1000 are inserted in this order into a plain BST. How much does a search cost now?

Practice

Real problems to lock it in, easiest first.

LeetCodeSearch in a Binary Search Tree beginner↗LeetCodeInsert into a Binary Search Tree intermediate↗LeetCodeValidate Binary Search Tree intermediate↗LeetCodeKth Smallest Element in a BST intermediate↗LeetCodeDelete Node in a BST intermediate↗