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 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.
0 votes 0 votes The number of ways in which n numbers x1<x2<⋯<xn can be inserted in an empty binary search tree, such that the resulting tree has height n−1 is 2n−1 answer is 64. iarnav answered Jan 7, 2018 edited Jan 7, 2018 by iarnav iarnav comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The number of ways in which n numbers x1<x2<⋯<xn can be inserted in an empty binary search tree, such that the resulting tree has height n−1 is 2n−1 iarnav answered Jan 7, 2018 iarnav comment Share Follow See all 0 reply Please log in or register to add a comment.