retagged by
49,476 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

Best answer
169 votes
169 votes
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).
edited by
201 votes
201 votes

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)

35 votes
35 votes
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
18 votes
18 votes
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
Answer:

Related questions

73 votes
73 votes
5 answers
1