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

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!}$

by

Plz chk this question

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

the above formula is to find number of BST..

according to me the answer should be 8..

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?
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?

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

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$

1 vote