Optimal Binary Search Tree (OBST)

Optimal Binary Search Tree (OBST)

Optimal Binary Search Tree (Optimal BST)

Optimal Binary Search Tree (Optimal BST)

Expected Cost Formula

Construction OF OBST

Find O.B.S.T for the data (Problem 1)

Find O.B.S.T for the data (Problem 2)

Expected Cost Formula

Construction OF OBST

Find O.B.S.T for the data (Problem 1)

Find O.B.S.T for the data (Problem 2)

Recurrence Relation (Dynamic Programming)

Cost for choosing $a_{k}$ as a root:

Final Recurrence

✅ 1. Cost Table $(C [i] [j])$

Table Initialization:

Filling the Table:

✅ 2. Root Table $(K [i] [j])$

Why K[i][j] is important?

Given Data

✅ Step 1 — Sort Keys

✅ Step 2 — Fill $C [i, i]$ (length = 1)

✅ Step 2 — Fill Table Using Formula

Base (main diagonal)

C[1,2]

C[2,3]

C[3,4]

C[1,3]

C[2,4]

C[1,4] (final)

Final 4×4 cost matrix $C$ (showing $i \leq j$ entries)

✅ Step 1 — Sort A

✅ Step 2 — Fill $C [i, i]$ (length = 1)

✅ Step 2 — Fill Table Using Formula

Base (main diagonal)

C[1,2]

C[2,3]

C[3,4]

C[1,3]

C[2,4]

C[1,4] (final)

Final 4×4 cost matrix $C$ (showing $i \leq j$ entries)

Recurrence Relation (Dynamic Programming)

Cost for choosing ak​​ as a root:

Final Recurrence

✅ 1. Cost Table (C[i][j])

Table Initialization:

Filling the Table:

✅ 2. Root Table (K[i][j])

Why K[i][j] is important?

Given Data

✅ Step 1 — Sort Keys

✅ Step 2 — Fill C[i,i] (length = 1)

✅ Step 2 — Fill Table Using Formula

Base (main diagonal)

C[1,2]

C[2,3]

C[3,4]

C[1,3]

C[2,4]

C[1,4] (final)

Final 4×4 cost matrix C (showing i≤j entries)

✅ Step 1 — Sort A

✅ Step 2 — Fill C[i,i] (length = 1)

✅ Step 2 — Fill Table Using Formula

Base (main diagonal)

C[1,2]

C[2,3]

C[3,4]

C[1,3]

C[2,4]

C[1,4] (final)

Final 4×4 cost matrix C (showing i≤j entries)

Cost for choosing $a_{k}$ as a root:

✅ 1. Cost Table $(C [i] [j])$

✅ 2. Root Table $(K [i] [j])$

✅ Step 2 — Fill $C [i, i]$ (length = 1)

Final 4×4 cost matrix $C$ (showing $i \leq j$ entries)

✅ Step 2 — Fill $C [i, i]$ (length = 1)

Final 4×4 cost matrix $C$ (showing $i \leq j$ entries)

Abhijeet Singh Rajput

@abhijeetsingh

Created

Dec 8, 2025

Last Modified

3 months ago

Let $a_{1}, a_{2}, \dots, a_{n}$ be the distinct keys ordered from the smallest to the longest and
Let $p_{1}, p_{2}, \dots, p_{n}$ be the probability of searching their
$C [i, j]$ be the smallest average number of comparisons made for a successful search in a binary search tree
$T_{i}^{j}$ (B.S.T) made of keys $a_{i}, a_{i + 1}, \dots, a_{j}$
- Where $i, j$ are integer indices
- and, $1 \leq i \leq j \leq n$

We only want $C [1, n]$ but to compute it, we must compute all smaller subproblems.

To build the optimal BST for keys
$a_{i}, a_{i + 1}, \dots, a_{j}$ :

We try choosing each key $a_{k}$ (where $i \leq k \leq j$ ) as the root.

If $a_{k}$ is root:

Left subtree:
$T_{i}^{k - 1} \to keys a_{i} \dots a_{k - 1}$
Right subtree:
$T_{k + 1}^{j} \to keys a_{k + 1} \dots a_{j}$

Both must be optimally arranged.

Cost = C [i, k - 1] + C [k + 1, j] + s = i \sum j p_{s}

The extra sum is because when a subtree becomes deeper, every key inside gains +1 comparison.

C [i, j] = i \leq k \leq j min (C [i, k - 1] + C [k + 1, j] + s = i \sum j p_{s})

Boundary case:

C [i, i - 1] = 0

If a tree assigns levels:

$x_{1}, x_{2}, \dots, x_{n}$

Then expected search cost is:

$\sum_{i = 1}^{n} p_{i} \cdot x_{i}$

When building an Optimal Binary Search Tree, the goal is to minimize the average search cost using the given probabilities of each key.

To compute this efficiently, we use dynamic programming, specifically two tables:

The table C[i][j] stores the minimum cost of constructing an optimal BST using keys from index i to j.
Main diagonal = 0, because when i == j, there’s no key → empty tree → cost is zero.
The given probabilities P[i] are placed just above the diagonal, since each key alone is its own OBST.

C[i][i] = 0
C[i][i+1] = P[i]

We compute values diagonally, moving from lower-left to upper-right.
Each entry C[i][j] represents the optimal cost of keys i…j.
The final value C[1][N] gives the minimum average search cost of the entire OBST.

To reconstruct the actual tree, we maintain another table:

K[i][j] stores the index of the key that gives the minimum cost for the subproblem (i, j).
This value represents the optimal root for that range.

Because once we know the root for each subproblem:

The left subtree is built from keys i to K[i][j] - 1
The right subtree is built from keys K[i][j] + 1 to j

Using this, we can recursively rebuild the full Optimal Binary Search Tree.

Keys = [A, B, C, D]
Prob = [0.1, 0.2, 0.4, 0.3]

Keys = [A, B, C, D]
Prob = [0.1, 0.2, 0.3, 0.4]

i/j	1	2	3	4
1	0.1
2	0	0.2
3	0	0	0.3
4	0	0	0	0.4

C [i, j] = k = i \dots j m i n (C [i, k - 1] + C [k + 1, j] + s = i \sum j p_{s})

$C [1, 1] = p_{1} = 0.1$
$C [2, 2] = p_{2} = 0.2$
$C [3, 3] = p_{3} = 0.3$
$C [4, 4] = p_{4} = 0.4$

s = 1 \sum 2 p_{s} = 0.1 + 0.2 = 0.3

k = 1 : k = 2 : C [1, 0] = 0 + C [2, 2] = 0.2 + 0.3 = 0.5 C [1, 1] = 0.1 + C [3, 2] = 0 + 0.3 = 0.4

C [1, 2] = min (0.5, 0.4) = 0.4

s = 2 \sum 3 p_{s} = 0.2 + 0.4 = 0.6

k = 2 : k = 3 : C [2, 1] = 0 + C [3, 3] = 0.4 + 0.6 = 1.0 C [2, 2] = 0.2 + C [4, 3] = 0 + 0.6 = 0.8

C [2, 3] = min (1.0, 0.8) = 0.8

s = 3 \sum 4 p_{s} = 0.4 + 0.3 = 0.7

k = 3 : k = 4 : C [3, 2] = 0 + C [4, 4] = 0.3 + 0.7 = 1.0 C [3, 3] = 0.4 + C [5, 4] = 0 + 0.7 = 1.1

C [3, 4] = min (1.0, 1.1) = 1.0

s = 1 \sum 3 p_{s} = 0.1 + 0.2 + 0.4 = 0.7

k = 1 : k = 2 : k = 3 : C [1, 0] = 0 + C [2, 3] = 0.8 + 0.7 = 1.5 C [1, 1] = 0.1 + C [3, 3] = 0.4 + 0.7 = 1.2 C [1, 2] = 0.4 + C [4, 3] = 0 + 0.7 = 1.1

C [1, 3] = min (1.5, 1.2, 1.1) = 1.1

s = 2 \sum 4 p_{s} = 0.2 + 0.4 + 0.3 = 0.9

k = 2 : k = 3 : k = 4 : C [2, 1] = 0 + C [3, 4] = 1.0 + 0.9 = 1.9 C [2, 2] = 0.2 + C [4, 4] = 0.3 + 0.9 = 1.4 C [2, 3] = 0.8 + C [5, 4] = 0 + 0.9 = 1.7

C [2, 4] = min (1.9, 1.4, 1.7) = 1.4

s = 1 \sum 4 p_{s} = 0.1 + 0.2 + 0.4 + 0.3 = 1.0

k = 1 : k = 2 : k = 3 : k = 4 : C [1, 0] = 0 + C [2, 4] = 1.4 + 1.0 = 2.4 C [1, 1] = 0.1 + C [3, 4] = 1.0 + 1.0 = 2.1 C [1, 2] = 0.4 + C [4, 4] = 0.3 + 1.0 = 1.7 C [1, 3] = 1.1 + C [5, 4] = 0 + 1.0 = 2.1

C [1, 4] = min (2.4, 2.1, 1.7, 2.1) = 1.7

i/j	1	2	3	4
1	$0. 1^{K = 1}$	$3 8^{K = 2}$	$1. 1^{K = 3}$	$1. 7^{K = 3}$
2	0	$0. 7^{K = 2}$	$0. 8^{K = 3}$	$1. 4^{K = 3}$
3	0	0	$0. 4^{K = 3}$	$1. 0^{K = 3}$
4	0	0	0	$0. 3^{K = 4}$

("0" denotes invalid $i > j$ entries; $C [i, i - 1] = 0$ used in computations.)

A = [5, 20, 10, 3]

P = [20, 7, 12, 9]

A = [3, 5, 10, 20]

P = [9, 20, 12, 7]

i/j	1	2	3	4
1	9
2	0	20
3	0	0	12
4	0	0	0	7

C [i, j] = k = i \dots j min (C [i, k - 1] + C [k + 1, j] + s = i \sum j p_{s})

$C [1, 1] = p_{1} = 9$
$C [2, 2] = p_{2} = 20$
$C [3, 3] = p_{3} = 12$
$C [4, 4] = p_{4} = 7$

s = 1 \sum 2 p_{s} = 9 + 20 = 29

k = 1 : k = 2 : C [1, 0] + C [2, 2] = 0 + 20 + 29 = 49 C [1, 1] = 9 + C [3, 2] = 0 + 29 = 38

C [1, 2] = min (49, 38) = 38

s = 2 \sum 3 p_{s} = 20 + 12 = 32

k = 2 : k = 3 : C [2, 1] = 0 + C [3, 3] = 12 + 32 = 44 C [2, 2] = 20 + C [4, 3] = 0 + 32 = 52

C [2, 3] = min (44, 52) = 44

s = 3 \sum 4 p_{s} = 12 + 7 = 19

k = 3 : k = 4 : C [3, 2] = 0 + C [4, 4] = 7 + 19 = 26 C [3, 3] = 12 + C [5, 4] = 0 + 19 = 31

C [3, 4] = min (26, 31) = 26

s = 1 \sum 3 p_{s} = 9 + 20 + 12 = 41

k = 1 : k = 2 : k = 3 : C [1, 0] = 0 + C [2, 3] = 44 + 41 = 85 C [1, 1] = 9 + C [3, 3] = 12 + 41 = 62 C [1, 2] = 38 + C [4, 3] = 0 + 41 = 79

C [1, 3] = min (85, 62, 79) = 62

s = 2 \sum 4 p_{s} = 20 + 12 + 7 = 39

k = 2 : k = 3 : k = 4 : C [2, 1] = 0 + C [3, 4] = 26 + 39 = 65 C [2, 2] = 20 + C [4, 4] = 7 + 39 = 66 C [2, 3] = 44 + C [5, 4] = 0 + 39 = 83

C [2, 4] = min (65, 66, 83) = 65

s = 1 \sum 4 p_{s} = 9 + 20 + 12 + 7 = 48

k = 1 : k = 2 : k = 3 : k = 4 : C [1, 0] = 0 + C [2, 4] = 65 + 48 = 113 C [1, 1] = 9 + C [3, 4] = 26 + 48 = 83 C [1, 2] = 38 + C [4, 4] = 7 + 48 = 93 C [1, 3] = 62 + C [5, 4] = 0 + 48 = 110

C [1, 4] = min (113, 83, 93, 110) = 83

i/j	1	2	3	4
1	$9^{K = 1}$	$3 8^{K = 2}$	$6 2^{K = 2}$	$8 3^{K = 2}$
2	0	$2 0^{K = 2}$	$4 4^{K = 2}$	$6 5^{K = 2}$
3	0	0	$1 2^{K = 3}$	$2 6^{K = 3}$
4	0	0	0	$7^{K = 4}$

("0" denotes invalid $i > j$ entries; $C [i, i - 1] = 0$ used in computations.)

$C [1, n]$

$P_{\dots}$

$P_{i, j}$

$P_{\dots}$