Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Question

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees.

For example, for $N$ = 3, $H$ = 3: There are 2 trees with $1$ as root, 1 tree with $2$ as root and 2 trees with $3$ as root.

Hence, $Sum$ = $2*(1) + 1*(2) + 2*(3) = 10$

I am trying to solve this problem by writing a function $f(n,h)$ which is related to $f(n-1,h-1)$ and $f(n-1,h)$ in some way, but unable to find the solution.

Note: All numbers $[1, N]$ must be present in the tree and the height should be $\le H$.

Answer 1

Let's solve a simpler problem first: How many binary search trees are there with $n$ nodes? Call this number $b_n$. We know $b_0 = b_1 = 1$. If you pick $k$ as the root ($1 \le k \le n$), you have $k - 1$ keys to distribute to the left and $n - k - 1$ to the right, so that:

$$ b_n = \sum_{1 \le k \le n} (b_{k - 1} + b_{n - k - 1}) $$

Shift the indices down, and note the symmetry of the sum to get:

$$ b_{n + 1} = 2 \sum_{0 \le k \le n} b_k $$

Define the generating function $B(z) = \sum_{n \ge 0} b_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get:

$$ \sum_{n \ge 0} b_{n + 1} z^n = 2 \sum_{n \ge 0} z^n \sum_{0 \le k \le n} b_k $$

Recognize some sums here:

$$ \frac{B(z) - b_0}{z} = 2 \frac{B(z)}{1 - z} $$

Pugging in $b_0 = 1$ solution is:

$$ B(z) = \frac{1}{3} + \frac{2}{3} \cdot \frac{1}{1 - 3 z} $$

so that (here $[\text{condition}]$ is Iverson's bracket, $1$ if the condition is true and $0$ if false):

$$ b_n = \frac{2 \cdot 3^n + [n = 0]}{3} $$

Now we are in position to solve your problem if there is no restriction on height. If the root of a binary search tree with $n$ nodes is $k$, there are $k - 1$ nodes in its left subtree and $n - k$ to the right, so the number of binary trees with root $k$ are $b_{k - 1} \cdot b_{n - k}$, and you are asking for:

$\begin{align} \sum_{1 \le k \le n} k b_{k - 1} b_{n - k} &= \sum_{1 \le k \le n} k \frac{2 \cdot 3^{k - 1} + [k = 1]}{3} \cdot \frac{2 \cdot 3^{n - k} + [k = n]}{3} \\ &= 1 \cdot \frac{2 \cdot 3^0 + 1}{3} \cdot \frac{2 \cdot 3^{n - 1}}{3} + n \cdot \frac{2 \cdot 3^{n - 1}}{3} \cdot \frac{2 \cdot 3^0 + 1}{3} + 4 \cdot 3^{n - 3} \sum_{2 \le k \le n - 1} k \\ &= (1 + n) \cdot 2 \cdot 3^{n - 2} + 4 \cdot 3^{n - 3} \left( \frac{n (n - 1)}{2} - 1 \right) \\ &= (2 n^2 + 4 n + 2) \cdot 3^{n - 3} \\ &= 2 (n + 1)^2 \cdot 3^{n - 3} \end{align}$

Answer 2

OK, do it right this time. Call the number of binary trees with $n$ nodes $C_n$ (the notation will come clear shortly). Then the number of binary trees with $0$ nodes is $C_0 = 1$, and a tree with $n + 1$ nodes with root $k$ is made of a $k - 1$ node tree to the left and a $n + 1 - k$ node tree to the right, so there are $C_{k - 1} C_{n + 1 - k}$ with root $k$, for a total of:

$\begin{align} C_{n + 1} &= \sum_{1 \le k \le n + 1} C_{k - 1} C_{n + 1 - k} \\ &= \sum_{0 \le k \le n} C_k C_{n - k} \end{align}$

It is well known that this gives the Catalan numbers, i.e.,

$$ C_n = \frac{1}{n + 1} \binom{2 n}{n} $$

Now the sum of the roots of all binary trees with $n$ nodes (note we don't restrict heights) is:

$\begin{align} \sum_{1 \le k \le n} k C_{k - 1} C_{n - k} &= \sum_{0 \le k \le n - 1} (k + 1) C_k C_{n - 1 - k} \\ &= \sum_{0 \le k \le n - 1} (n - k) C_k C_{n - 1 - k} \end{align}$

The last one is by noting symmetry of the trees with root $1$ and $n$, and generally $k$ and $n + 1 - k$. But so:

$\begin{align} \sum_{1 \le k \le n} k C_{k - 1} C_{n - k} &= \frac{1}{2} \left( \sum_{0 \le k \le n - 1} (k + 1) C_k C_{n - 1 - k} + \sum_{0 \le k \le n - 1} (n - k) C_k C_{n - 1 - k} \right) \\ &= \frac{1}{2} \cdot (n + 1) \sum_{0 \le k \le n - 1} C_k C_{n - 1 - k} \\ &= \frac{n + 1}{2} C_n \\ &= \frac{1}{2} \binom{2 n}{n} \end{align}$