I'd like to know if anyone could help me verify a recursive formula for the minimum possible number of nodes a binary search tree would require to be balanced. So far, I know that the recursive solution for the maximum possible number of nodes is $M(d)=2M(d−1)+1$, where d is the depth of the BBT. I assume that for the minimum number it may be: $M(d)=2M(d)$ as the non-recursive formula is simply $2^d$. Is this correct, or am I thinking along the wrong sort of lines?
[Math] Minimum number of nodes in balanced binary search tree
combinatoricsgraphing-functionstrees
Related Solutions
I can think of no definitions of binary tree and distinct that would produce six distinct binary trees.
There are $14$ plane binary trees, i.e., rooted binary trees in which left and right offspring are distinguished. If left and right offspring are not distinguished, there are only three rooted binary trees:
* * *
| | / \
* * * *
/ \ | |
* * * *
|
*
If you consider unrooted trees, the last two of these are the same: there are only two unrooted binary trees.
If you consider labelled trees, the numbers go up considerably: unrooted the chain graph with four vertices already can be labelled in $12$ ways, so there’s no way to get just six.
Maybe this diagram will be clearer. It shows the full balanced binary trees of depths 1, 2, 3, and 4. The tree of depth 0 has no nodes at all.
The first tree has 1 node. The tree with depth 2 has twice as many (in green and blue) plus a root node (in red), which makes $2\cdot1+1 = 3$.
The tree with depth 3 has twice as many again (in green and in blue) plus a root node (in red), which makes $2\cdot3+1 = 7$.
The tree with depth 4 has twice as many again (in green and in blue) plus a root node (in red), which makes $2\cdot7+1 = 15$.
There are two things to know about this. First, if $M(d)$ is the number of nodes in the full binary tree of depth $d$, then $M(d+1) = 2M(d) + 1$. You can see that from the diagram, since a tree of depth $d+1$ consists of two copies of the tree of depth $d$ (one in green and one in blue) plus a root node (in red). Each tree has the same kind of structure:
The second thing to know is that $M(d) = 2^d-1$ for all $d$. I will show that now.
I claim that the number of nodes in the tree of depth $d$ is always $2^d-1$. Suppose this was wrong, that there were some tree with some other number of nodes. Then among all such trees, there must be one with the smallest possible depth. Let's say that the smallest tree for which the claim fails has depth $m$.
Now evidently $m>1$, because you can see from the diagram that the claim is true for trees of depth 1. But a tree of depth $m>1$ is made of two smaller trees of depth $m-1$ (one in green, and one in blue) plus one root node (in red).
We said that the depth-$m$ tree is the smallest one for which the claim fails. So the claim is true for the smaller trees of depth $m-1$: they have $2^{m-1}-1$ nodes each. Then the depth $m$ tree has $2^{m-1}-1$ green nodes, $2^{m-1}-1$ blue nodes, and one red node, for a total of $\color{green}{2^{m-1} - 1} + \color{blue}{2^{m-1} - 1} + \color{red}{1}$. This adds up to $2\cdot2^{m-1} - 2 + 1 = 2^m - 1$, so the claim is true for our tree of depth $m$ also. This contradicts our assumption that there was a tree for which the claim was false, so our assumption must be wrong, and so there is no such tree and there is no such $m$.
Related Question
- [Math] The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.
- [Math] Minimum Number of Nodes for Full Binary Tree with Level $\lambda$
- [Math] In binary tree, number of nodes with two children when number of leaves is given
- [Math] Binary Trees: relationship between height and number of children
Best Answer
Hint You want a minimum node depth $d$ balance binary search tree. What happens if you take a maximum node tree of depth $d-1$ and add a single node?