How can I find a Binary tree from a given Traversal Method?

Question

How can I find a binary tree from a given traversal method (inorder,post-order,pre-order)?

Answer 1

The wikipedia article for inorder, post-order, pre-order tree traversal is here:

http://en.wikipedia.org/wiki/Tree_traversal.

The tree you are looking for starts at the node that matches your search term.

Answer 2

If you want to restore original tree using the traversal result, then I have some bad news for you - there is no unambiguous solution. There will be several trees that can produce same traversal result.

For example for inorder traversal following trees will produce the same result: 1, 2, 3

    2           3       1
   / \         /         \
  1   3       2           2
             /             \
            1               3

Answer 3

You can't do this by it with only one traversal (Inorder, Preorder or Postorder).

It can be done If Inorder & Preorder traversal of a tree is given :

1. First element of preorder will be Root of tree. (suppose it is A)
2. Searc root in Inorder so all nodes which are left of root are Inorder of left subtree and right nodes are Inorder of right subtree. calculate number of nodes in left side of root say L.
3. In postorder from 2nd L nodes will be preorder of left subtree and after that are preorder of right subtree.

So we found root element and devided our Inorder in to Inorder of left subtree, Inorder of right subtree and Preorder in to preorder of left subtree and preorder of right subtree. So We can do this by recursion until only one node is left.

Similarly we can do for Inorder and Postorder where root will be the last element of the post order.

Answer 4

(Ok, since we've decided that the amended question should be here, posting my answer there as well)

The Postorder and Inorder traversals of a binary tree are given below.Is it possible to obtain a unique binary tree from these traversals?

It is possible.

In postorder traversal (left-right-root) the root node of the whole tree is always the last (in your case it's A). In inorder traversal (left-root-right) the nodes before the root belong to the left subtree and the nodes after the root---to the right one. Since we've already determined the root, we can determine the nodes in the left subtree and in the right subtree.

Having determined that, we are able to separate left and right subtree in postorder list. So, now we've determined the left and right subtrees and root node:

postorder: left|right|root
inorder  : left|root|right

Now we just have to recursively construct left and right subtrees. Fin.