### Unique binary search tree from n distinct nodes node noofedges binarysearchtree binarytree noofvertices    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (3373)

How many unique binary search tree can be formed from n distinct nodes?

 Posted: 6 years ago Updated: 6 years ago 0 0 Edit 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$$. public int countTrees(int numOfKeys){ if(numOfKeys < = 1) return 1; else{ int sum = 0; int left, right, root; for(root = 0; root < numOfKeys; root+++){ left = countTrees(root - 1); right = countTrees(numOfKeys - root); sum = sum + (left * right); } return sum; } }