# Facts about internal and external path lengths of binary tree

While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.

My book specifies some facts about these as follows:

1. $S_n=1+\frac{U_0+U_1+...+U_{n-1}}{n}$

2. For large $n$, $S_n=2 \log_en$

3. Internal path length $I_n$ of binary tree with $n$ internal nodes is at least $n \times \lg(n/4)$ and at most $\frac{n(n-1)}{2}$

Where

• $n \rightarrow$ number of (internal) nodes in binary search tree
• $S_n \rightarrow$ average number of comparisons required for successful search in a random binary search tree with $n$ internal nodes
• $U_n \rightarrow$ average number of comparisons required for unsuccessful search in a random binary search tree with $n$ internal nodes
• $I_n \rightarrow$ Internal path length of binary tree with $n$ internal nodes
• $E_n \rightarrow$ External path length of binary tree with $n$ internal nodes (not used above)

Out of these I can complete reason out only the maximum internal path length statded in point 3 as follows: It occurs in degenerate binary tree (point 3.6 on this page). In this case, internal path length is $0+1+2+...+(n-1)=\frac{n(n-1)}{2}$.

About the minimum internal path length, the book says following:

The minimum internal path length occurs in case of the best case binary tree i.e. almost complete binary tree (maximum possible number of nodes having both children). Such tree has $(n+1)$ external nodes at height no more than $\lg {n}$. Multiplying these and applying the below property: $$E_n=I_n+2n$$ we get the bound: $$(n+1)\lg n-2n<n \lg (N/4)$$

Q1. However I am still not clear how the above bound is obtained

Q2. Also I did not understood how first two facts out of above 3 are derived and especially what the first fact is meant to imply.

• What is a random binary search tree for you? Wikipedia (en.wikipedia.org/wiki/Random_binary_tree) lists two possibilities. – Yuval Filmus Apr 24 '16 at 14:47
• I just stated what my textbook says. However I feel it should hold for "any given binary search tree". And I feel my textbook also means the same by the word "random". The book does not say anything in specific about randomness. Honestly thats why I did not put much thoughts about how the trees should be obtained "randomly" as put in wikipedia while asking the question. – Maha Apr 24 '16 at 15:05
• Without defining a distribution here, you cannot talk about expectation. Expectation is not a property of "every" tree, it is a property of a "random" tree (more accurately, of a distribution over trees). – Yuval Filmus Apr 24 '16 at 15:06
• I think I lack depth...but book also says $S_n=\frac{(n+1)}{n}U_n-1$, which is easy to reduce to $S_n=\frac{I+n}{n}$, which I feel holds for any given binary search tree. The first two facts are from not-so-standard book, though I dont feel it can be wrong. However the third one is from Sedgewick's book and he has put it not in the context of $S_n$ and $U_n$, so "randomness" might not apply to third fact. In question above, I put all together since I wasnt aware that randomess has more meaning to it as you stated. – Maha Apr 24 '16 at 15:21

I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m>1$, if the current (ordered) contents of the tree at the previous step are $x_1<\ldots<x_{m-1}$, we choose an interval uniformly at random among the $m$ intervals $$(-\infty,x_1),(x_1,x_2),\ldots,(x_{m-2},x_{m-1}),(x_{m-1},\infty),$$ choose an arbitrary element from the interval, and insert it to the binary tree. A random binary search tree of size $n$ is obtained by stopping this process at step $n$, and erasing the values at the vertices.

You can show that the arbitrary choices do not affect the distribution. Also, the relative order of the elements of the tree at step $n$ (in order of insertion) is a random permutation on $n$ elements.

You haven't explained what you mean by $S_n$ and $U_n$ exactly, so I assume you are using the following definitions:

• Let $T_n$ be a random binary search tree of size $n$ before erasing the values. Choose one of the $n$ elements at random, and run binary search on $T_n$ and this element. The average number of comparisons in this process is $S_n$.

• Let $T_n$ be a random binary search tree of size $n$ before erasing the values, and let $x$ be the random element inserted by the process at the following step. Run binary search on $T_n$ and $x$. The average number of comparisons in this process is $U_n$.

First fact

Given these definitions, the first fact is easy to prove. Suppose that the element we search for was inserted at step $i$. Note that the distribution of $i$ is uniform over $\{1,\ldots,n\}$. Inserting $i$ at step $i$ requires $U_i$ comparisons in expectation. It takes us the same number of steps to reach this element at the current experiment, and one more comparison to verify that we have indeed found the element. The formula follows.

Second fact

Here we need a non-trivial argument, outlined in the Wikipedia article. Let the sorted elements in the tree be $x_1<\cdots<x_n$. Suppose that the element we look for is $x_i$. The search goes through an element $x_j$ if $x_j$ is an ancestor of $x_i$. Thus, given $i$, the average number of comparisons is $$\sum_{j=1}^n \Pr[\text{x_j is an ancestor of x_i}].$$ Now $x_j$ is an ancestor of $x_i$ if among all elements in $\{x_i,\ldots,x_j\}$ (or $\{x_j,\ldots,x_i\}$), $x_j$ was the first inserted. Since the true order of insertion is a random permutation of $x_1,\ldots,x_n$, we conclude that $$\Pr[\text{x_j is an ancestor of x_i}] = \frac{1}{|i-j|+1}.$$ Choosing a random $i$, this shows that \begin{align*} S_n &= \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n \frac{1}{|i-j|+1} \\ &= \frac{1}{n} \sum_{i=1}^n \frac{1}{|i-i|+1} + \frac{2}{n}\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{1}{i-j+1} \\ &= 1 + \frac{2}{n}\sum_{i=1}^n \sum_{j=2}^i \frac{1}{j} \\ &= 1 + \frac{2}{n}\sum_{i=1}^n (H_i - 1) \\ &= \frac{2}{n} \sum_{i=1}^n H_i - 1 \\ &= \frac{2(n+1)}{n} (H_{n+1} - 1) - 1. \end{align*} Here $H_i$ is the $i$th harmonic number, and we used the identity $\sum_{i=1}^n H_i = (n+1)(H_{n+1}-1)$. It is well-known that $H_i = \ln i + \gamma + O(1/i)$ and that $\ln (n+1) = \ln n + O(1/n)$, and so \begin{align*} S_n &= 2\left(1+\frac{1}{n}\right) (\ln n + \gamma - 1 + O(1/n)) - 1 \\ &= 2\ln n + 2\gamma - 3 + \frac{2\ln n}{n} + O\left(\frac{1}{n}\right). \end{align*}

Third fact

The upper bound is given by a path, in which case $I_n = 0 + 1 + \cdots + (n-1) = n(n-1)/2$. For the lower bound, it is easier to consider first the special case $n = 2^m-1$. In that case, the lower bound is given by a balanced binary tree. Such a tree has $2^k$ nodes at depth $k$, and so $$I_n = \sum_{d=0}^{m-1} 2^k k = 2^m (m-2) + 2 = (n+1)\log_2 \tfrac{n+1}{4} + 2.$$ More generally, if $n = 2^m-1+x$ for $x < 2^m$, it is best to put the $x$ extra nodes at depth $m$, and so \begin{align*} I_n &= 2^m(m-2) + 2 + mx \\ &= (m-2)(2^m+x) + 2(x+1) \\ &= (m-2)n + m-2 + 2(x+1). \end{align*} Notice that $m \leq \log_2 (n+1) < m+1$, that is, $m = \lfloor \log_2 (n+1) \rfloor$. Therefore $$I_n = n\lfloor \log_2 (n+1) \rfloor + O(n) = n \log_2 n + O(n).$$ To get an actual lower bound, notice that $$I_n \geq (m-2)n + m > n \log_2 \frac{n+1}{4} \geq n\log_2 \frac{n}{4}.$$