The number of different binary trees that can be formed?

Question

binary tree, where each node has no more than two child nodes, child nodes can contain links to their parents.

we do not differentiate the nodes and all nodes are considered identical. How can we find the number of different binary trees that can be formed with N identical nodes.

for example: if 3 nodes, then 5 diff trees
if 7 knots, then 429 trees

Answer 1

Now, if you really want to understand this, instead of just getting (or experimenting to find) an answer, you can check out “The Art of Programming,” Volume 4, Fascicle 4: Generating All Trees .

Answer 2

Recursion is your friend!

pseudo code:

 numOfTrees(n): return trees(n).size(); trees(n): if (n==1) return new list of single node; big_trees = new empty list; for (small_tree : trees(n-1)) for (big_tree : addSingleNode(tree)) big_trees.insert(big_tree); return big_trees; addSingleNode(tree): trees = new empty list; for (leaf : getLeaves(tree)) { trees.insert(tree.clone().addLeftChild(leaf, node)); trees.insert(tree.clone().addRightChild(leaf, node)); } return trees; 

getLeaves () is implementation dependent, if you have a linked list with all the sheets then it will be fast, otherwise you may need to traverse the tree checking the leaves (which is O (n) in_order).

memory is not very efficient, but it solves the problem by simple recursion, where at each stage I take trees and look through all the leaves and add a new node in all possible ways.

Answer 3

(2n)! / [(P + 1)! * P!]

take a look at:

http://www.theory.csc.uvic.ca/~cos/inf/tree/BinaryTrees.html