Maximum number of distinct binary tree possible with 4 nodes

Question

what is the maximum number of distinct binary tree is possible with 4 nodes? ans is 6 but how? acc to me it should be 14

What is your definition of distinct? – Aryabhata Feb 02 '12 at 19:22 — Aryabhata, Feb 02 '12 at 19:22
means different binary tree can possible – Ashish Feb 02 '12 at 19:23 — Ashish, Feb 02 '12 at 19:23

score 1 · Answer 1 · answered Feb 02 '12 at 20:05

I can think of no definitions of binary tree and distinct that would produce six distinct binary trees.

There are $14$ plane binary trees, i.e., rooted binary trees in which left and right offspring are distinguished. If left and right offspring are not distinguished, there are only three rooted binary trees:

   *                      *                      *   
   |                      |                     / \  
   *                      *                    *   *  
  / \                     |                    |  
 *   *                    *                    *  
                          |  
                          *

If you consider unrooted trees, the last two of these are the same: there are only two unrooted binary trees.

If you consider labelled trees, the numbers go up considerably: unrooted the chain graph with four vertices already can be labelled in $12$ ways, so there’s no way to get just six.

Maximum number of distinct binary tree possible with 4 nodes

1 Answers1