top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How many number of binary tree possible for N number of nodes?

+4 votes
425 views

Is there any formula.

posted Oct 21, 2013 by Vikas Upadhyay

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Do we need to consider the node value.

1 Answer

+2 votes

It will be 2n!/(n+1)!n!

See the following code

int countTrees(int numKeys) {

  if (numKeys <=1) {
    return(1);
  }
  else {
    // there will be one value at the root, with whatever remains on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...
    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
      left = countTrees(root - 1);
      right = countTrees(numKeys - root);

      // number of possible trees with this root == left*right
      sum += left*right;
    }

    return(sum);
  }
} 
answer Oct 22, 2013 by Bob Wise
...