InOrder + PostOrder = PreOrder

Traditional Problems Trees Problems

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

Consider the following binary tree : 

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

The Input

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

The Output

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

Solution (Yogy Namara) :

The basic form of an InOrder traversal is :
  left subtree - root - right subtree
The basic form of a PostOrder traversal is :
  left subtree - right subtree - root
We know that the root of the tree is the last node of the PostOrder 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 PostOrder traversal as well, since they have the same number of nodes in it.

To print the PreOrder traversal, we find the root of the tree, print it, and recursively find the root of the left and the right subtree.

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