Number of binary search tree of height $6$

Question

The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is______ .

Note: The height of a tree with a single node is $0$.

---

My attempt :

As we need height of tree is $6$, and we have seven distinct number. Other than root node we have $2$ option at each level either node is left node or right node only.

Therefore, total number of BSTs $= 1\times2\times2\times2\times2\times2\times2 =1\times2^6=1\times64=64$ Answer.

Can you explain in formal way or alternative way, please?

Answer 1

I think the best way to go is to prove a more general property by induction.

Let $P(n)$ be: The number of ways in which $n$ numbers $x_1<x_2<\dots<x_n$ can be inserted in an empty binary search tree, such that the resulting tree has height $n-1$ is $2^{n-1}$

$P(1)$ is easy to prove.

Assume that $P(n)$ hold for some $n$ and show that $P(n+1)$ is true. small hint:

To do this notice that the root can only be $x_1$ or $x_{n+1}$, then apply the induction hypothesis and it should give you $P(n+1)$.

Then to prove your statement you use $P(7)$.

I hope it helps.

Answer 2

You get the maximum height $h=6$ with $7$ nodes, at degenerate cases, that is when the numbers inserted are in ascending or descending order. So, only the insertion orders $(1,2,3,4,5,6,7)$ and $(7,6,5,4,3,2,1)$ will give height $6$. So the answer is $2$.