PreOrder + InOrder = PostOrder

Traditional Problems Trees Problems

This problem is similar to the InOrder + PostOrder = PreOrder problem.

Consider the following binary tree : 

       A          Input
      / \         PreOrder  = ABCDEFG
     B   E        InOrder   = CBDAEGF
    / \   \
   C   D   F      Output
          /       PostOrder = CDBGFEA
         G
You are required to print the PostOrder traversal of the tree, given its PreOrder and InOrder traversals.

The Input

In the input file there will be several cases. Each case consists of two strings, the valid PreOrder and InOrder traversal of the tree.

The Output

For each case, print the PostOrder traversal of the tree.

Solution (Yogy Namara) :

The basic form of a PreOrder traversal is :
  root - left subtree - right subtree
The basic form of an InOrder traversal is :
  left subtree - root - right subtree
We know that the root of the tree is the first node of the PreOrder traversal. In the InOrder traversal, this same node is located between the left subtree and the right subtree. Now, we can determine the left subtree and the right subtree in the InOrder traversal, and in the PreOrder traversal as well, since they have the same number of nodes in it.

To print the PostOrder traversal, we find the root of the tree, recursively find the root of the left and the right subtree, and finally print the root of the current tree.

yogy-n@sby.mega.net.id GeoCities