Binary Search Tree

Created

Nov 16, 2025

Last Modified

3 months ago

Binary Search Tree

A Binary Search Tree (BST) is a special type of binary tree.
It can be empty, but if it’s not empty, it follows these rules:

Each node contains a unique key — no duplicates.
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.
Recursion rule:
Both left and right subtrees must also be valid BSTs following the same properties.

Number of Comparisons (Sastry & Bhandari)

The number of comparisons required to search for a key in a BST equals the number of nodes visited until the key is found - basically, the depth/level where the key exists.

Total Number of BSTs with N Keys

The total number of distinct BSTs that can be formed using N keys is given by the Nth Catalan Number.

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

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

C (2) =^{4} C_{2} \cdot \frac{1}{3}

C (4) = 14

Recurrence Relation

1. Best Case (Perfectly balanced tree)

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

2. Worst Case (Skewed tree — like a linked list)

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

3. Average Case $(H e i g h t \approx O (lo g n))$

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

Binary Search Tree

Binary Search Tree

Number of Comparisons (Sastry & Bhandari)

Total Number of BSTs with N Keys

Recurrence Relation

1. Best Case (Perfectly balanced tree)

2. Worst Case (Skewed tree — like a linked list)

3. Average Case (Height≈O(logn))

3. Average Case $(H e i g h t \approx O (lo g n))$