#bst tree

Question

The number of BST possible with 6 node numbered 1,2,3,4,5 and 6 with exactly one leaf node

Comments

should be 32?

---

one leaf node ==> it should be chain of nodes !

let denote the nodes with A,B,.....

A ------------- B ------------- C -------------- D ---------- E ------------- F

those links are either left or right ==> 2${^\text{no.of links}} = 2^5$ = 32 structures possible !

it is BST, So in each structure, you can place a unique value for the Node ==> 32*1 = 32

Answer 1

I think its 2^5 =32

as it's given, it has only 1 child for  the given BST

Hence it can have a structure of form 1-2-3-4-5-6 ; 6-5-4-3-2-1; 6-5-1-4-3-2 etc.

similarly, we have 2^5=32 possibilities

Answer 2

no of BST possible with 6 node is = 192

Comments

Please explain

---

(2n C n) / (n+1)