CODEWITHSUNDEEP
calgorithmbinary-tree
JackieBoy
JackieBoy

Reputation: 93

number of different binary trees that can be formed?

binary tree, where each node has at most two child nodes, child nodes may contain references 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.

eg: if 3 nodes then 5 diff trees
if 7 nodes then 429 trees

Upvotes: 5

Views: 1397

Answers (3)

Dervin Thunk
Dervin Thunk

Reputation: 20119

Now, if you really want to understand this, instead of just getting (or experimenting to find) the answer, you can check out "The Art of Computer Programming", Volume 4, Fascicle 4: Generating all trees.

Upvotes: 1

Kumar Alok
Kumar Alok

Reputation: 2612

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

have a look at:

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

Upvotes: 1

davin
davin

Reputation: 45525

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 dependant, if you have a linked list with all leaves, then it will be quick, otherwise you might have to traverse the tree checking for leaves (which is O(n) in_order).

not very memory efficient, but it solves the problem by simple recursion, where at every stage i take the trees and go over all the leaves and add my new node in every possible way.

Upvotes: 1

Related Questions