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.

\boxed{C(n) = \\ ^{2n}C_n \cdot\left(\frac{1}{n + 1}\right)}

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

C(2)=^4C_2\cdot\frac13

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

T(n)=Tn/2)+C