Binary Tree

Question

How many numbers of binary tree can be created with 4 nodes which when traversed in post order gives the sequence D, C, B, A?

1. 14

2. 15

3. 10

4. 16

Please Explain.

Is there any formula?

Answer 1

Here one thing to note :

No of trees with given preorder traversal  =  No of trees with given postorder traversal

                                                                                  =  No of trees with given inorder traversal

                                                                                  = No of BSTs

                                                                                  = No of unlabelled binary trees

                                                                                  =  Catalan Number  [  C(2n,n) / (n+1) ]

Here n  =  4

So substituting  n = 4 in the expression we get :

Number of binary trees with given postorder traversal    =   C(8,4) / 5

                                                                                 =  [ 8 * 7 * 6 * 5 ] / [ 1 * 2 * 3 * 4 * 5 ]

                                                                                 =  14 

Comments

sir, it means number of labeled binary tree with n nodes and having same inorder/preorder/postorder traversal= catelan no.

AND

number of labeled binary tree with n nodes= catalan no. * n!

plzz clearify me 

---

Yes u r right..:)

---

thank you sir for your helpful response :)

Answer 2

No. Of trees with given postorder= no.of trees with unlabeled nodes =C(2n,n)/n+1
 For n=4
No.of trees possible=C(8,4)/5
=14