CODEWITHSUNDEEP
algorithmbinary-treeinorderpostorder
dibyendu
dibyendu

Reputation: 543

How to get the post order traversal of a BINARY TREE (NOT binary search tree), given only its inorder traversal

I've given the result of in-order traversal of a binary tree (not binary search tree) as:

E, D, B, A, G, F, H, C

Now I've to find out the result of the post-order traversal of the same tree for which the in-order traversal is given.

Can anyone suggest me any algorithm for this ?

P.S: Is there any way to sketch the tree itself from the in-order result ?

Upvotes: 0

Views: 546

Answers (1)

rks
rks

Reputation: 920

You can't do that. Your example might represent multiple trees, for example :

E                       D
 \                     / \
  D                   E   B
   \                       \
    B                       A
     \                       \
      A                       G                          ...
       \                       \
        G                       F
         \                       \
          F                       G
           \                       \
            H                       C
             \
              C

You need at least two orders to reconstruct the tree, and you can only give an order when you have the tree at hand.

Upvotes: 2

Related Questions