# Prove that balanced binary search tree has lowest expected cost

Take numbers from 1 to 100. Put all of them in a binary search tree. Now, one of those 100 numbers is picked uniformly at random and given to us. We'd like to find it in the binary search tree. The tree should be constructed in a way that the expected number of comparisons in minimal. It's intuitive that a balanced tree where we always go to the middle element and select it as the next child will be optimal. In other words, go to the median, 50 and make it the root. Then go to the median of the left elements, 25 and make it the left child and the median of the right elements, 75 and make it the right child and so on.

But I'm unable to prove this in general. For the case of 100, one could simply create the binary tree with this strategy and verify that every level has the largest possible elements. But how to do it for general n?

Firstly, note the following claim:

Claim: Let $$S$$ be any set of $$n$$ elements. Let $$B$$ be any binary tree with $$n$$ empty nodes. Then, there exists a mapping of $$S$$ to the nodes of $$B$$ such that $$B$$ is a binary search tree of set $$S$$.

Proof: The claim follows since inorder traversal of the tree can be mapped to sorted set of elements in $$S$$.

Next, note that searching an element in a binary search tree (BST) has cost equal to the level of that element in the tree. Therefore, the expected cost of searching an element in the tree is $$\sum_{i \in S} \ell(i)/n$$, where $$\ell(i)$$ is the level of element $$i$$ in the tree.

Let $$B$$ be a balanced binary search tree over $$S$$, with maximum level $$L$$ (assume the root node has level $$1$$). Let $$B'$$ be any unbalanced binary search tree with level $$\geq L+1$$. Let $$N_o$$ be any node at level $$\geq L+1$$. The node can be moved to a lower level since there exists an empty location with level $$\leq L$$. The level of node $$N_o$$ decreases by at least $$1$$. Repeat this process till all the nodes at level $$\geq L+1$$ are moved to levels $$\leq L$$. This is feasible since there exists a tree $$B$$ where all nodes can fit in levels $$\leq L$$. For each node moved, the level of node decreases. However, the tree will no longer be a search tree. However, the above claim states that there exists a mapping of nodes to the elements in $$S$$ that makes the tree "binary search tree". Thus, the expected cost of the new tree, which is balanced, is smaller than the unbalanced tree.

Why the tree constructed by "choosing median recursively" gives the minimum expected cost?

Proof: Let $$k$$ be such that $$n = 2^{k}-1+m$$, where $$m < 2^{k}$$. Then, after the first iteration, each subtree has at least $$\lfloor (2^{k}-1+m-1)/2 \rfloor$$ nodes $$\geq 2^{k-1} - 1 + m'$$, where $$m' < 2^{k-1}$$. Inductively, after $$k-1$$ iterations, the number of nodes in any subtree is at least $$1$$. Thus, all the levels from $$1$$ to $$k-1$$ are completely filled. These nodes constitute a total of $$2^{k}-1$$ nodes. Therefore, the nodes at the last level are $$m$$. The last level is $$k$$, which is $$= \lceil \log n \rceil$$. This is the minimum possible level for a binary tree. Moreover, since all the nodes at lower levels are filled completely, $$m$$ is the minimum number of nodes that appear at the last level. This also implies that $$\sum_{i \in S} \ell(i)$$ is minimum; thus the expected cost of searching in the tree is minimum.

• but how to prove that the median strategy will always result in a balanced binary search tree? Feb 27 at 7:15
• Yes, meant balanced. Feb 27 at 7:20
• It is easy to see that the height of the tree is at most $\lceil \log n \rceil$. And, you cannot accommodate $n$ nodes in any tree of height $< \lceil \log n \rceil$. Does that answers your question? or you also want to show that the number of nodes at the last level are minimum? Feb 27 at 7:34
• @RohitPandey Added the details to the answer. Feb 27 at 8:17
• @RohitPandey Oh. It was a typo. I have changed it to $m < 2^{k}$. Thanks for pointing it out. Does it look fine now? Feb 29 at 8:50

The cost for searching a node in a BST is the node's depth in the BST.

What you need to show is that the average depth is lower in a balanced BST than in any BST.

An informal way to see it is that if the BST is not balanced, then you could delete one of its leaf to put it in a lower depth.

Note that if the set of value of your BST is $$S$$, then for any binary tree structure of size $$|S|$$, there is exactly one BST that can be labeled with $$S$$. What that means is that to prove your result, you only have to work on tree structure, and not on labelling.