No of trees can be constructed from given Inorder/Preorder/Postorder traversal

1
votes

I know one cannot construct a tree without having both Inorder and Preorder/postorder traversals. Because for a given (only Inorder/Preorder/postorder) there could be a possibility of generating more number of trees. Are there any algorithms or mechanism one can compute the number of unique trees from a given (only Inorder/Preorder/postorder traversal).

Eg : a b c d e f g this is my Inorder traversal.

How many unique trees that can be constructed with the given Inorder traversal.

I tried them is google but none of the explanations are clear

Any help would be appreciated...

3
algorithmdata-structurestree
one cannot construct a tree without having both Inorder and Preorder/postorder traversals that is one bold statement: Given keys unique in the subtree they root in preorder (equivalently postorder) and information about their sequence from left to right (explicitly or by order (search tree)), one can unambiguously reconstruct a tree. (Come to think of it, this seems to need a restriction to binary tree (implied with inorder).) – greybeard
(I think it possible with no two equal keys parent and child is sufficient - finding a linear construction looks a challenge.) – greybeard

3 Answers

5
votes

Well the algorithm is as follows:

Let, P(N) denote the number of trees possible with N nodes. Let the indexes of the nodes be 1,2,3,...

Now, lets pick the root of the tree. Any of the given N nodes can be the root. Say node i has been picked as root. Then, all the elements to the left of i in the inorder sequence must be in the left sub-tree. Similarly, to the right.

So, total possibilities are: P(i-1)*P(N-i)

In the above expression i varies from 1 to N.

Hence we have,

P(N) = P(0)*P(N-1) + P(1)*P(N-2) + P(2)*P(N-3)....

The base cases will be:

P(0) = 1 
P(1) = 1

Thus this can be solved by using Dynamic Programming.

2
votes

Note that a particular traversal is just a way of labeling the nodes in a tree, so that the number of possible binary trees is the same for any two traversals of the same length. The number of binary trees with n nodes is given by the n-1st Catalan number.

0
votes

The formula

(2n)!/ (n)!(n+1)!

OR

2n * C(n) / (n+1)

gives the number of possible binary trees for any given INORDER/PREORDER/POSTORDER traversal.