# The number of ways of insertion in binary search tree

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

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$$,

• Very nice! I put your numbers in the Online Encyclopedia of Integer Sequences, et voila: oeis.org/A076616 "Number of permutations of {1,2,...,n} that result in a binary search tree (when elements of the permutation are inserted in that order) of height n-1 (i.e., the second largest possible height)." oeis.org/A014480 "Number of binary trees of size n and height n-1" Sep 21 at 8:57

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)$$

• Hello, I tried to work out the problem. Though the problem statement is not clear to me, but the interpretation you chose is a viable interpretation, but in that for $n=4$ I got the answer as $6$ instead of $10$. I tried to verify using a complete example and an entire program to work out in a brute force manner. I wonder if as per your assumptions $P(n)=2^n$? I guess it is $P(n)=2^{n-1}$. Please correct me if I am wrong. :) Sep 21 at 7:38
• @AbhishekGhosh Nicely pointed out. It is indeed $2^{n-1}$. I will edit the answer, Thanks! Sep 21 at 7:40

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

• There are clearly more than just $10$ options... Anyways, checking all possible ways is error-prone, and it isn't clear that there are so little options such that this can be done by hand. Sep 20 at 15:41
• It's a 7 element BST with 6 elements in one side (height=5), in general there are 7 ways to separate an element (then 2 sides L,R) but not all of them can fit as a BST
– ShAr
Sep 20 at 16:02
• What about their inner ordering? Sep 20 at 16:32
• It may had slipped out of your mind, that elements in one side of a degenerate BST must be sorted; just where to insert the 7th node
– ShAr
Sep 20 at 16:46
• You can totally make make more than $7$ options in total. For example, here is a valid tree: $1$ is the root, $6$ is the right child, $7$ is the right child of $6$, and the rest of the tree being left children of $6$. The point is that its not necessarily "one shape" for the tree and you have to choose the position for the last node. You can create more "shapes" which will in turn create more options for positions Sep 20 at 16:55