What is the minimum and maximum number of leaf nodes a binary search tree can have? [closed]

$\begingroup$

By leaf node i mean a node that does not have a child. What i want is an expression to show the relation between 'n' which is number of nodes and the minimum & maximum number of leaf nodes a BST can have.

$\endgroup$

1 Answer

$\begingroup$

There's one leaf if there's only one node.

Otherwise there are always at least two leaves in any tree. If you consider the root not to be a leaf, even if it has degree 1, then a path has only one leaf.

In a binary tree, every node has degree 1, 2, or 3. Say $n_i$ nodes have degree $i$. Since it's a tree, there are $n-1$ edges, and we have$$n_1 + 2 n_2 + 3 n_3 = 2e = 2n - 2 = 2(n_1+n_2+n_3) -2.$$So $n_3 = n_1 - 2$. With $n = n_1 + n_2 + n_3$, this lets us write$$n_1 = \frac{n - n_2 + 2}{2}$$.

The root either has degree one or two. If it's degree one, the number of leaves is $n_1 - 1$, which is largest for a given $n$ when $n_2$ is 0:$n_1 - 1 = \frac{n}{2}$.

If the root has degree two, then the number of leaves is equal to $n_1$, and is largest for a given $n$ when $n_2 = 1$ (the root is the only degree-two node.) Then the number of leaves is $n_1 = \frac{n+1}{2}$.

$\endgroup$