What would be the time complexity of counting the number of all structurally different binary trees?
Posted
by ktslwy
on Stack Overflow
See other posts from Stack Overflow
or by ktslwy
Published on 2010-03-29T02:23:14Z
Indexed on
2010/03/29
2:33 UTC
Read the original article
Hit count: 379
complexity
|binary-trees
Using the method presented here: http://cslibrary.stanford.edu/110/BinaryTrees.html#java
12. countTrees() Solution (Java) /** 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. */ public static 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); } }
I have a sense that it might be n(n-1)(n-2)...1, i.e. n!
© Stack Overflow or respective owner