can anyone answer this please 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 5, is ____
srestha, Vikas Verma, Shaik Masthan, Rishav Kumar Singh, Shivani gaikawad Please check
To get BST of height 5, max( height of left subtree,height of right subtree) should be 4 [Height of tree= 1 +max Height of subtree]
There can be only two possible roots for such BST -> 2 and 6.
If you fix 2 as the root the left subtree gets 1 and the right subtree gets (3,4,5,6,7). Now treat this as a new problem (like the one in the link you provided).
"The number of ways in which the numbers 3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 4"
This will be 2^4=16.
Now '1' can be inserted at anytime in between the insertions but 2 has to be inserted at first. So 2_3_4_5_6_7_. So there are 6 places where 1 can be inserted.
So, 6*16 =64.
Again fix root as 6. The right subtree will get 7 and the left will get (1,2,3,4,5). Following the same method again we get 16 BSTs.
Here 7 can be inserted at any time but 6 has to be the first one to be inserted.
Again there are 6 possible spaces where 7 can be inserted.
So 6*16=64.
64+64=128.
But if the number of unique BSTs with height 5 is asked then it should be 16+16=32 because insertion of 1 for 1st case and 7 for 2nd case results into the duplicate BSTs.
Do let me know if there is any mistake.