Tag Info

Hot answers tagged


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 ...


Suppose that the root is on level $n$. If $n=0$ or $n=1$, none of the nodes pays or receives anything, so each node has a balance of $0$. (To avoid clutter I omit the dollar sign.) If $n=2$, the $4$ nodes on level $0$ pay $7$ each and receive nothing, so they end up with a balance of $-7$; the $2$ nodes on level $1$ neither pay nor receive and have a balance ...

Only top voted, non community-wiki answers of a minimum length are eligible