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

How can a we even make 64 valid BSTs from only {1..7} with height 6...I think only 2 trees will be possible strictly left skewed and righ skewed who satisfy the definition of a BST....please someone explain the reason

---

​

 Logic 1 : Since there are 7 nodes and we need height 6 BST so only skewed BST's (or Linear BST possible)

Now to calulate all such structures we can think that except leaf every internal node must have exaclty one child and it can be either left or right child.

In a tree with n nodes that is fully skewed, there are n-1 internal nodes.

Each of these n-1 nodes must have exactly one child, and that child can be either a Left child or a Right child.

Thus skewed binary trees possible with nodes 7 is 2*2*2*2*2*2 = 64 

For a skewed BST, the relationship between the physical structure and the required insertion order is one-to-one.

 

So the Total Insertion Order will be 64 (Skewed BST structure) * only 1 insertion order possible = 64

but note for other BST like this :

 

 

 

 

 

There 2 insertion order : 1,2,3 or 1,3,2

 

Logic 2 : 

If u go for any element other than the minimum (1) or maximum ele (7) for the root node then the BST Tree cannot reach the height 6

L0 (Root) : Either 1 or 7 (2 choices)

L1 : Out of remaining 6 number u must pick the current minimum or maximum (for e.g if u pick 7 as the root, then for L1 node u can only pick 1 or 6); otherwise the tree will not be skewed.

Similarly there are 2 choices for L2, L3, L4, L5  AND L6 has only 1 remaining number left so only 1 choice

Hence here the ans is 2^6 = 64

​

 

---

All 64 tree structures has height 6 and for each tree, inorder will be 1,2,3,4,5,6,7

Hence total 64 ways to insert 1,2,3,4,5,6,7 in all those empty BST.

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

after 4,4 how wel eft with 2 choices, i mean we can't repeat numbers. @aritra nayak

---

very well

---

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.

---

Why is it marked as wrong ? Can someone please explain ?

---

she has a typo that bst can't have two children where they can have two children

---

@Divya_Sruthi_R, I don't think it's a typo. The BST in question here cannot have any node with 2 children since we need it to have a height of 6.

The solution is on the right track but looks like where she went wrong is listing the choices:

"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)" -- this is wrong since one of 1 and 7 would still be a choice for the second level (either (2, 7) or (1, 6) would be the choices based on what was chosen for level 1)

Answer 4

Let $f(n)$ be the number of the binary search trees of $(n-1)$ height (i.e. maximum height) using numbers $(x+1,x+2,x+3,...,x+n)$ where $x \in \mathrm{R}$.

For $n=1$, the answer is $1$ since there is only one node of height $0$. $\therefore f(1)=1$

For $n=2$, the answer is $2$ since there are two cases of height $1$ starting $2$ as root and $1$ as root . $\therefore f(2)=2$ 

 

For $n=3$, the answer is $4$.

 

 

Let's observe how $f(n)$ is growing from $f(n-1)$. We can add the $n^{\mathrm{th}}$ node taking as the root to the trees of $(n-1)$ nodes $(1,2,3,...,n-1)$. For this case of $(n-1)$ nodes, there are $f(n-1)$ trees. Still there are more cases to be taken. Take $1$ as the root and the rest $(n-1)$ nodes are $(2,3,...,n)$ for which there are also $f(n-1)$ trees. [ For example, we can add $3$ as the root to trees of two nodes $(1,2)$. Besides taking $1$ as the root, there can be trees using $(2,3)$.  That's why $f(3)=f(2)+f(2)=2+2=4$ ]

 

So $f(n)=\{\text{trees using }(1,2,3,...,n-1)\text{ nodes having }n^{\mathrm{th}}\text{ node as the root}\}+\{\text{trees using }(2,3,4...,n)\text{ nodes having 1 as the root}\}$

$\begin{align}\therefore f(n)&=f(n-1)+f(n-1)\\ &=2f(n-1)\\&=2^2f(n-2)\\&=2^3f(n-3)\\&=\cdots\\&=2^{n-1}f(1)\\&=2^{n-1}; ~[\because f(1)=1] \end{align}$

 

$\therefore f(7)=2^{7-1}=2^6=64$.

So the correct answer is $64$.

 

Comments

Good recursive approach.

---

Nice explanation @techbd123

---

great approach!

Answer 5

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

Comments

is que ka ans 2^6 =64 h

kyuki node 7 ke liye height 6 ka ya to left skewed tree bnenga ya right so

isme har level pr do possibility hogi  accept 4 level

---

 @Khushbu makode not always skewed tree zig zag tree also possible

im right ?

 

---

ha yha har level pr 2 possibility h na left ya right

---

ok thanku

Answer 6

But  , here your resulting tree height must be 6.......

so it is only possible when your tree is either left-skew or right-skew ....

and above tree is binary search tree..........

so either you can insert in increasing order (right-skew tree) or insert in decreasing order (left-skew tree).....

so only possible way is 2....................

Emphasized point=>  (1) height must be 6      (2)  Binary search tree

think about it !!!!

Comments

4

                                         7

                                   6

                            5

                   3

            2

     1

 

this is one kind of tree possible so ur answer is wrong

---

you can also from  start from 1 and make the same tree bending towards right and more like taking 1 as root after that seven as right child then 5 as left child and so on ..... and many more keep in mind that at each level you have to insert only single node and for each location you have two choice either choose smaller one or bigger one and their are 6 level so 2^6 = 64 possible trees

---

what do you mean by"we don't need the entire tree to be left or right skewed" ,then how will it fulfill the criteria of bst?