GATE CSE 2016 Set 2 | Question: 40

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

Comments

What if height is given as 5?

@Arjun @SachinMittal1

---

Each node has two choices to go left or right until level 5. => 2^5

The remaining one node can be inserted for any of the 6 nodes. But If we insert for last node the height will be 6.
So remaining node has only 5 possibilities.

Final answer: 5*(2^5)

---

It may lead to overcounting

Answer 1

We need to fill $7$ levels with $7$ elements. So, at each level, we have exactly $2$ possible options like $1$ and $7$ for root- one corresponding to going left and the other corresponding to going right. This is the same for all levels up to 6 giving $2^6 = 64$ possible ways. In extreme cases, we can get fully left-skewed or right-skewed trees and otherwise, the shape of the tree will be some form of zigzag (every node having a single child).

Comments

@ air1ankit  please correct!!  you mistyped level 7 contains 2 ways. but that’s not possible cause in last level we only left with 1 key. So, their is only 1 way for level 7.

---

same here

thank you guys to make me understand

---

i also think the same @Kiyoshi

Answer 2

WELL its RECURRENCE QUESTION ,,,,but for that need to observe the pattern ..first and then THE 
RECURRENCE RELATION WILL BE N(h)=2N(h-1)

Comments

Why do we choose the extremes only in this case?

---

Thanks a lot sir

---

Such a nice explanation @Deepesh Kataria helped me to understand the question 

Answer 3

A simple way to solve this question:
See that we need height of 6 and we have 7 elements at hand. So obviously any node in BST can't have two children.Now think about if root node is 2 or 3 or 4 or 5 or 6,then that root must have 2 children.So root must be either 1 or 7.Let denote root as 1st level.
So at 1st level, we either can choose 1 or 7(2 choices)
At 2nd level,similarly we can choose 2 or 6(2 choices)
At 3rd level,similarly we can choose 3 or 5(2 choices)
At 4th level,similarly we can choose 4 or 4(2 choices)
At 5th level,similarly we can choose 5 or 3(2 choices)
At 6th level,similarly we can choose 6 or 2(2 choices)
At 7th level, we will have only 1 number remaining.
So total number of BSTs possible=2^6=64

Comments

thanks for the explanation bro :-)

---

Hello aritra

I marked your answer wrong as i found it right answer with wrong solution, observe more carefully , you will know why.

---

@Rupendra Choudhary Sir it's a good answer. Just edit it and make it right.

Answer 4

there can be total 2^6 skew tree ,and being a BST there is only one permumation for a given BST .

ytotal 2^6 diffrnect skew trees are possible