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$. DS gatecse-2016-set2 data-structures binary-search-tree normal numerical-answers + – Akash Kanase asked Feb 12, 2016 retagged Jun 30, 2017 by Silpa Akash Kanase 49.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments ayush_27 commented Aug 18, 2023 reply Follow Share What if height is given as 5? @Arjun @SachinMittal1 1 votes 1 votes Teja25 commented Sep 6, 2023 reply Follow Share 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) 0 votes 0 votes ayush_27 commented Sep 6, 2023 reply Follow Share It may lead to overcounting 0 votes 0 votes Please log in or register to add a comment.
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 ambikesh answered Nov 26, 2018 ambikesh comment Share Follow See all 0 reply Please log in or register to add a comment.
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\}$ At the start all numbers are available. We can either choose $1$ or $4$. Let’s choose $4$, i.e. the maximum; the available set now becomes $\{1, 2, 3\}$ We can either choose $1$ or $3$. Let’s choose $1$, i.e. the minimum; the available set now becomes $\{2, 3\}$ 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$ ashutoshbsathe answered Dec 1, 2020 ashutoshbsathe comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes A Simple Alternative method:------ Assume a BST of Full binary Tree of height 6 (where root height is 0) you can see from root to every leaf node there is unique path , and total no. of this unique path is same as no. of possible ways in which elements {1,2,3, 4, 5, 6, 7 } of height 6 BST can be created. (and in BST structure elements can be filled in unique way) This unique path can is same as no. of leaves in full binary tree =$2^{height}$ (when height of root node is 0) Hence answer is $2^{6}$ means 64 Kamlesh Maurya answered Sep 8, 2023 edited Sep 9, 2023 by Kamlesh Maurya Kamlesh Maurya comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The Recurrence Relation for the no. of binary search tree for 'n' nodes(distinct) with height 'n-1' will be NBST(n-1)=NBST(n-2)+NBST(n-2) ; Base condition:NBST(0)=1 and NBST(1)=2 ; So NBST(6) =2*NBST(5)=2*2*NBST(4)=2*2*2*NBST(3)=2*2*2*2*NBST(2)=2*2*2*2*2*NBST(1)=26=64. Eg:Take 3 nodes 1,2,3.No.of BST with height 2 is (i)With root as 1 ,the no. of possible BST will be 2(ie.NBST(1)) , (ii)With root as 3 ,the no. of possible BST will be 2(ie.NBST(1)) and (iii)With root as 2,there will not be any BST of height 2. So 2+2 =4. MaheshK answered Feb 13, 2016 reshown Feb 17, 2016 by MaheshK MaheshK comment Share Follow See all 0 reply Please log in or register to add a comment.