retagged by
49,506 views
168 votes
168 votes
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$.
retagged by

17 Answers

3 votes
3 votes
Since the height of the tree must be 6, it should have 6 edges intuitively the tree is skewed in this case.

Each edge has 2 choices i.e. it can a left branch or right branch. (/ or \)

So we can have 2^6 possible structures with height 6 and 7 nodes and for each structure there is only 1 way to fill up the values to form a binary search tree.
3 votes
3 votes
at every level we should either select the minimum or the maximum as if we select any intermediate elements the hieght cant reach 6

so at level one 1 or 7  (7 elements left)

 at level 2  either minimum or maximum of the remaining based on the selection at level 1 may be we select from 2,7 or 1,6 hence two choices this gives height 1  (6 elements left)

 at level 3 either min or max this gives hieght 2 (5 left)

at level 4 min or max gives hieght 3 (4 left)

at level 5 min or max gives hieght 4  (3 elements left)

at level 6 min or max gives hieght 5  (2 elements left)

at level 7 we dont have choice 1 element left hence 2*2*2*2*2*2 gives 64
1 votes
1 votes

With n nodes, the maximum height that can be achieved is  n-1  when the tree is left or right skewed
here at each level, we have two choices except level 4 which has only one choice:-
two make tree skewed :
at level 1  (1,7)
at level 2  (2,6)
at level 3  (3,5)
at level 4  (4,4)
at level 5  (5,3)

and so on
so the number of ways is: 2*2*2*1*2*2*2 =64

1 votes
1 votes

We have been given 7 numbers and are asked to find the number of possible BSTs with height 6. This means that we have to find number of trees with maximum height.

How do we maximize height of a BST ? By skewing it ! How can we skew “effectively” ?

Maintain a list of available numbers and always pick the maximum or minimum from the list when choosing the next number in the ordering

Consider a small set of values : $\{1, 2, 3, 4\}$

  1. At the start all numbers are available.
  2. We can either choose $1$ or $4$. Let’s choose $4$, i.e. the maximum; the available set now becomes $\{1, 2, 3\}$
  3. We can either choose $1$ or $3$. Let’s choose $1$, i.e. the minimum; the available set now becomes $\{2, 3\}$
  4. We can either choose $2$ or $3$ and our tree has been formed.

In total, we made 3 independent binary decisions so the total possibilities are $2^3 = 8$. The 2 trees formed by taking $4$ first followed by $1$ are visualized below : (dot represents no children)

The same discussion can be extended for the given question as well to give the answer $2^6 = 64$

Answer:

Related questions

73 votes
73 votes
5 answers
1