Optimal Binary Search Tree (OBST)

Optimal Binary Search Tree (OBST)

Optimal Binary Search Tree (Optimal BST)

Optimal Binary Search Tree (Optimal BST)

Recurrence Relation (Dynamic Programming)

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)

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)

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)

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)

Dec 8, 2025

Updated 4 days ago

3 min read

The Optimal Binary Search Tree (OBST) is a dynamic programming technique used to construct a binary search tree that minimizes the average search cost based on the probability of accessing each key. Given a sorted set of keys and their respective search frequencies, OBST ensures that more frequently accessed elements are placed closer to the root, reducing the overall number of comparisons required during search operations. By solving smaller subproblems and combining their results, it efficiently determines the structure of the tree that yields the minimum expected search time, making it highly useful in applications like database indexing and compiler design.

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}$