in DS
748 views
3 votes
3 votes
What is the number of binary trees with $4$ nodes which when traversed in pre-order gives the sequence A, B, C, D?
in DS
by
748 views

4 Answers

3 votes
3 votes
Best answer

We have the elements of the binary tree and also the order of the elements - be it inorder, preorder or postorder. Now, to get a different binary tree preserving this order, we can only change the structure of the binary tree. i.e., our problem reduces to the number of structurally different binary trees possible for $n=4$ here. This is same as

    Number of distinct binary trees possible with $n$ unlabelled nodes
    Number of binary search trees possible with $n$ nodes

And is given by $n^{th}$ Catalan number. The proof of this is simple and is given here:

http://gatecse.in/number-of-binary-trees-possible-with-n-nodes/

$\frac{2n!}{n+1!*n!}$

selected by

4 Comments

Plz chk this question

A,B,C,D here should be leveled nodes and traversed preorder
0
0
this is asking for preorder travesal...

the above formula is to find number of BST..

according to me the answer should be 8..

please suggest
0
0
What is answer 14 or something else? Someone please clarify.!!
0
0
3 votes
3 votes
1)             A                                    5)                A                                 9)              A
                                                           
          B        D                                            B                                                B

     C                                                      C          D                                               C

2)         A                                       6)            A                                               D

    B             D                                                     B                         10)           A

         C                                                        C           D                             B

3)        A                                       7)                     A                                          C

    B          C                                                 B                                                           D

             D                                              C                             11)        A

4)        A                                           D                                                    B

      B        C                                 8)          A                                                  C

                    D                                                B                                                    D

                                                                 C                                  12)         A

                                                                        D                                                  B

                                                                                                                  C

                                                                                                                         D

 13)             A                                                      14)                    A

                         B                                                                                   B

                                C                                                                  C

                           D                                                             D

1 comment

edited by
B can be A node's left child as well as right child for some tree?
0
0
0 votes
0 votes
1)             A

          B        D

     C

2)         A

    B             D

         C

3)        A

    B          C

             D

4)        A

      B        C

                    D

I got these 4 trees. Can anybody explain how rest 10 trees could be formed?

2 Comments

you can go one more level down.
0
0
I got more 8( B:left,4 combiations, B:right,4 combinations) trees, but what about 2 trees?
0
0
0 votes
0 votes

We know formulae to both

  • The total number of unlabelled binary trees
  • The total number of labelled binary trees

We've to figure out which one is to be applied here.

We'll need to obtain all the structurally independent binary trees, and then decide which node is A or B or C or D for that structurally independent tree — to get the given pre-order sequence.

Structurally independent $\equiv$ unlabelled binary trees.

So, 4th Catalan number.

$\frac{8*7*6*5}{5*4*3*2}=14$

Answer:

Related questions