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!}$
We know formulae to both
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$
64.3k questions
77.9k answers
243k comments
79.7k users