Binary Search Tree

Nov 16, 2025

Updated 1 day ago

3 min read

Binary Search Tree Basics Explained

A Binary Search Tree (BST) is one of the most important data structures in computer science, sitting at the heart of efficient search algorithms and dynamic data storage. It's a special type of binary tree where every node's position is determined by its key value — making search, insertion, and deletion all predictable and efficient.

BST Properties

A binary search tree can be empty. If it is not empty, it must satisfy all four of these rules:

Unique keys — Each node contains a unique key; no duplicates allowed.
Left subtree rule — Every key in the left subtree is smaller than the root's key.
Right subtree rule — Every key in the right subtree is greater than the root's key.
Recursive rule — Both the left and right subtrees must themselves be valid BSTs.

These properties are what make a BST useful for search algorithms — at every node, you can eliminate half the remaining tree from consideration, similar to binary search on a sorted array.

Number of Comparisons in a BST

The number of comparisons required to search for a key in a BST equals the number of nodes visited from the root until the key is found. This is simply the depth (level) at which the key exists in the tree.

Root is at depth 1 → 1 comparison
A node at depth 3 → 3 comparisons
A node at depth $h$ → $h$ comparisons

So the search cost is directly tied to the height of the tree, which is why balancing a BST matters.

Total Number of Distinct BSTs with N Keys

The total number of structurally distinct binary search trees that can be formed using $N$ keys is given by the $N$ th Catalan Number:

C (n) = (n 2 n) \cdot \frac{1}{n + 1}

Examples

For $n = 2$ :

C (2) = (2 4) \cdot \frac{1}{3} = \frac{4 \times 3}{2} \times \frac{1}{3} = 6 \times \frac{1}{3} = 2

Two distinct BSTs can be formed with 2 keys — one left-skewed, one right-skewed.

For $n = 4$ :

C (4) = (4 8) \cdot \frac{1}{5} = 70 \times \frac{1}{5} = 14

Fourteen distinct BSTs can be formed with 4 keys.

The Catalan numbers grow rapidly — for $n = 10$ , $C (10) = 16796$ — showing how many structural variations are possible even for small BSTs.

Recurrence Relations for BST Search

The time complexity of searching in a BST depends on the tree's shape. There are three cases, each with its own recurrence.

Best Case — Perfectly Balanced Tree

When the tree is perfectly balanced, each search halves the remaining nodes:

T (n) = T (n /2) + C

This solves to $O (lo g n)$ — the ideal case. The tree height is $⌊ lo g_{2} n ⌋$ .

Worst Case — Skewed Tree

When keys are inserted in sorted order, the BST degenerates into a linked list (all nodes on one side):

T (n) = T (n - 1) + C

This solves to $O (n)$ — the worst case. Every search must traverse all $n$ nodes. This is why a sorted input is the adversarial case for a BST, and why self-balancing trees (AVL, Red-Black) exist.

Average Case

On average, with random key insertion, the expected height of a BST is approximately $O (lo g n)$ :

T (n) = T (n /2) + C

This also solves to $O (lo g n)$ , making the BST efficient in practice for random data.

BST Complexity Summary

Operation	Best Case	Average Case	Worst Case
Search	$O (lo g n)$	$O (lo g n)$	$O (n)$
Insert	$O (lo g n)$	$O (lo g n)$	$O (n)$
Delete	$O (lo g n)$	$O (lo g n)$	$O (n)$

The worst case $O (n)$ occurs when the tree is completely skewed — motivating the use of balanced BST variants. For the recurrence derivations behind these complexities, see Binary Search Recurrence Relation and Asymptotic Notation.

Also Check These:

Binary Search Recurrence

Asymptotic Notation

Optimal BST (OBST)

Algorithm Design

References:

BST Operations — GeeksforGeeks