# Binary Tree Question

Discussion in 'School Work Help' started by ThatGuy, Mar 8, 2012.

1. ### ThatGuy Well-Known Member

186
16
0
I'm working on binary search trees for CS class, does anyone know a good way of recursively putting all the nodes into a list?
The way i'm doing it right now works, but it produces a list with nested lists inside it.
However, given the operations i can use on the list, i'm not sure if i can flatten it.

#1

3
1
0
3. ### TutorIndia New Member

3
1
0
/*
For the key values 1...numKeys, how many structurally unique
binary search trees are possible that store those keys.

Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.
*/
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);
}
}

#3
Last edited: Mar 13, 2013