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.
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. shriram s 1 answered Jul 10, 2017 shriram s 1 comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Venkat Sai answered Nov 8, 2017 Venkat Sai comment Share Follow See all 2 Comments See all 2 2 Comments reply Mudrakola Karthik 3 commented Jun 11, 2018 i edited by Mudrakola Karthik 3 Jun 11, 2018 reply Follow Share nice explaination 0 votes 0 votes Rajesh Panwar commented Sep 1, 2019 reply Follow Share thanks 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.