__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.

too much kaadhaa ?

ReplyDelete