749 views

4 Answers

Best answer
3 votes
3 votes

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

1 votes
1 votes
2 answers
1
Arjun asked Oct 10, 2016
764 views
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____
6 votes
6 votes
5 answers
3
0 votes
0 votes
1 answer
4
Arjun asked Oct 10, 2016
283 views
Consider the array given below:20 10 9 8 7 6 5It isa full binary tree in array representationa complete binary tree in array representationa max-heap in array representat...