Unique binary search tree from n distinct nodes
  • node
  • noofedges
  • binarysearchtree
  • binarytree
  • noofvertices
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2538)

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


Posted Answers

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;
}
}

You need to Sign In to post your solution.