No of BTS's

Question :

Given a number N, find the number of binary search trees(BST) possible with numbers 1,2....N

for E.g. if N = 2 , no. of BSTs with node-values 1 and 2 = 2
if N = 3 , no. of BSTs with node-values 1,2 and 3 = 5


Solution:

recursive sol for the same

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

Powered by ScribeFire.