The number of ways of insertion in binary search tree

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 5, is _________.

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

What I have tried: Since It has height=5, we have 4 options for root $1,2,6,or$ $7$. One element will be alone either on the left side or right side. Now we have 5 elements and we have to make a height of 4 which can be done in 2^4 ways.

So total = $2^2 \times 2^4 = 2^6$

Answer 1

The language of the question is a not quite clear to me. The question is open to two possible interpretations.

---

Interpretation 1:

Problem: For a given $n$ we need to find the number of permutations of $\langle 1,2,3,..,n\rangle$ such that if we build a binary search tree using that permutation as an input sequence we shall get a binary search tree of height $n-2$.

Let $f(n)$ denote the function such that for a given input $n$, it gives the answer to our problem above.

Now we can generate the formula for $f(n)$ in a generalized manner, but it shall be longer. Rather let us consider an example case to get the intuition and the general case could be easily derived from it.

Let $n=7$, then we need to consider permutations of $\langle 1,2,3,4,5,6,7\rangle$. Let us consider the structure of the binary tree formed and using that let us compute the number of required permutations.

If $1$ is the root, (then $1$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the right subtree [of height (n-3)] of the root. The number of such permutations shall be given by $f(n-1)$.

Similarly if $7$ is the root, (then $7$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the left subtree of the root. The number of such permutations shall be given by $f(n-1)$.

If $2$ is the root then $2$ has to be first element for the current subproblem. $1$ is to the left of root and the remaining $n-2=5$ elements are to the right of root. Now using these $n-2=5$ elements we can form a chain of length $n-3=4$ and starting from the root we shall have a height of $n-2=5$ for the entire tree. A little work out shall show that there are $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$.

In the subtree outlined with green the dotted edges shows just the possible structure and not the actual edges.

But for each of these $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$, $1$ can be interspersed anywhere so we shall have $(n-1)$ possible ways for each such $2^{n-3}$ permutations.

Just as the above situation we shall have have for root $6$, a total of $(n-1)*2^{n-3}$ permutations.

But for $3,4,5$ as the root we shall not be able to form a desired tree as both the left and right subtree in such cases shall fall short of the required number of elements to form a subtree of height $(n-3)$.

For an arbitrary $n$ we can have only the highest, second highest, lowest and second lowest as the root.

So we have,

$$f(n)= 2*f(n-1)+2(n-1)*2^{n-3}$$

Now we require a base case. Which is as follows, for $n=3$, we shall two possible input sequence.

So, $$f(n)=2 \text{ if n=3}$$

So using table method we have,

$f(3)=2$

$f(4)=16$

$f(5)=64$

$f(6)=208$

$f(7)=608$

A simple C program by me which verifies this, the program simply uses brute force method,asks for $n$, then generates all permutations of $\langle 1,2,.. n\rangle$. For each permutation inserts the elements into a empty BST keeping track of the height. If height equals $n-2$ then it outputs $\text{YES}$ beside that permutation and at the end, prints the total count of such $\text{YES}$s.

---

Interpretation 2:

Problem: For a given $n$ we need to find the number of structures of binary search trees of height $n-2$ using permutations of $\langle 1,2,3,..,n\rangle$ as input sequence.

Let $g(n)$ denote the function such that for a given input $n$, it gives the answer to our problem above.

Now we can generate the formula for $g(n)$ in a generalized manner, but it shall be longer. Rather let us consider an example case to get the intuition and the general case could be easily derived from it.

Let $n=7$, then we need to consider the structure of the binary tree formed using permutations of $\langle 1,2,3,4,5,6,7\rangle$.

If $1$ is the root, (then $1$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the right subtree [of height (n-3)] of the root. The number of such subtrees shall be given by $g(n-1)$.

Similarly if $7$ is the root, (then $7$ has to be first input element for the current subproblem) then the remaining $n-1(=6)$ elements can be placed in the left subtree of the root. The number of such subtrees shall be given by $g(n-1)$.

If $2$ is the root then $2$ has to be first element for the current subproblem. $1$ is to the left of root and the remaining $n-2=5$ elements are to the right of root. Now using these $n-2=5$ elements we can form a chain of length $n-3=4$ and starting from the root we shall have a height of $n-2=5$ for the entire tree. A little work out shall show that there are $2^{n-3}$ possible permutations of $\langle 3,4,..,n\rangle$ each of which forms a unique structure of binary search tree.

In the subtree outlined with green the dotted edges shows just the possible structure and not the actual edges.

Note that now we need not consider interspersing $1$ in each of $2^{n-3}$ permutations above, each such interspersing shall result in the same binary search tree structure.

Just as the above situation we shall have have for root $6$, a total of $2^{n-3}$ binary search trees.

But for $3,4,5$ as the root we shall not be able to form a desired tree as both the left and right subtree in such cases shall fall short of the required number of elements to form a subtree of height $(n-3)$.

For an arbitrary $n$ we can have only the highest, second highest, lowest and second lowest as the root.

So we have,

$$g(n)= 2*g(n-1)+2*2^{n-3}=2*g(n-1)+2^{n-2}$$

Now we require a base case. Which is as follows, for $n=3$, we shall two possible input sequence but only binary tree structure.

So, $$g(n)=1 \text{ if n=3}$$

So using table method we have,

$g(3)=1$

$g(4)=6$

$g(5)=20$

$g(6)=56$

$g(7)=144$

---

An example using $n=4$,

Answer 2

Let $T(n)$ denote the number of ways in which $n$ distinct numbers can form a binary tree of height $n-2$.

Let $P(n)$ denote the number of ways in which $n$ distinct numbers can form a binary tree of height $n-1$.

Then, $T(n) = 2 \cdot T(n-1) + 2 \cdot P(n-2)$

The first two $T(n-1)$ terms are due to choosing the smallest and the largest elements as roots. The second two $P(n-2)$ terms are due to choosing the second-smallest and second-largest elements as roots.

Also, $P(n) = 2 \cdot P(n-1)$. Here, the two $P(n-1)$ terms are due to choosing the smallest and the largest elements as roots.

Therefore, $P(n) = 2^{n-1}$ since $P(1) = 1$.

Now, compute the values of $T(n)$ for different values of $n$.

For $n = 3$, $T(3) = 1$ (base case)

For $n = 4$, $T(4) = 2 + 4 = 6$

For $n = 5$, $T(5) = 12 + 8 = 20$

For $n = 6$, $T(6) = 40 + 16 = 56$

For $n = 7$, $T(7) = 112 + 32 =144$

The general formula for $T(n)$ is $2^{n-3} + 2^{n-2} \cdot (n-3)$

Answer 3

To have height 5, then it's an almost degenerate tree; ie you simply check possible ways to have only one node in left or right

Coming out of root, 1st level, 2nd,...
I think there are 10 options, but you have to check them manually maybe some of them cannot happen for this set of numbers

The point is the main property of

Binary Search Trees (left child < parent, right child ≥ parent)

with the constrain of height=5

necessities that 6 nodes must be in sorted order with the 7th in different places; each color in the picture represents a way, and there are other 6 if we reverse the direction

Total=12