A,B,C,D here should be leveled nodes and traversed preorder

Dark Mode

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

0

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$