How many unique binary search tree can be formed from n distinct nodes?
We can create binary search tree with each node as the root at a time. If we consider node \( k \) as the root there will be \( k-1 \) nodes in the left subtree and \( n-k \) nodes in the right subtree and there can be a certain number of possible left and right subtrees. For \( n \) number of nodes, the number of possible binary search tree will be \( N(k)=\sum_{i=1}^{n} N(k-1)N(n-k)=(\frac{1}{n+1})^{2n} C_n \). This is called \( n^{th} \) catalan number. \( e.g,\ k=4 \), \( N(4)=14 \). |