#of BST

Question

Find number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having 6 as root and height of 4 ?

please explain in detail ...

Comments

i got 20
keep 6 as root then you have 4 options on the left node to 6 {5,4,2,1} and not 3 (you cannot build BST with height 4)

let's try 5 on the left then you have 4 options {4,3,2,1} and they will give you {1,2,2,1} unique trees

total trees 6 and that will be same for 1 just the left and right nodes will change and form unique trees

we have tried 5 and 1 on the left node its time for 2 and 4

if you keep 4 on the left of 6 then there is a compulsory 5 on the right of 4 so you can create unique trees with {1,2,3} with remaining height 3 so that are 5 - 1 = 4 (one is removed when root is 2 otherwise height issues)

so 6 - 4 gives you 4 trees and same 6-2 will give

 

so total = 6+6+4+4 = 20
i might be wrong :)