Find postorder traversal of a binary tree from its inorder and preorder sequence

Write an efficient algorithm to find postorder traversal of a binary tree from its inorder and preorder sequence.


 

For example, consider below tree:

Print Binary Tree


Input: 

Inorder Traversal:  { 4, 2, 1, 7, 5, 8, 3, 6 }
Preorder Traversal: { 1, 2, 4, 3, 5, 7, 8, 6 }

 
Output:

Postorder Traversal is: 4 2 7 8 5 6 3 1

 
Simple solution is to construct the binary tree from given inorder and preorder sequences, and then print postorder traversal by traversing the tree.

We can avoid constructing the tree by passing some extra information in a recursive postorder call. In simple recursive postorder call, left subtree is processed first, followed by the right subtree, and finally the node is printed. We can do something similar for printing the postorder traversal.

We start with the root node whose value would be the first item in the preorder sequence. The idea is to find boundaries of the left and right subtree of current root node in the inorder sequence. To find the boundaries of left and right subtree, we search for index of the root node in inorder sequence. Now all keys before the root node in inorder sequence becomes part of the left subtree and all keys after the root node becomes part of the right subtree. If we repeat this recursively for all nodes of the tree, we will end up doing a postorder traversal of the tree. This is demonstrated below in C++ –

 

Download   Run Code

Output:

Postorder Traversal is: 4 2 7 8 5 6 3 1

 
The time complexity of above solution is O(n) and requires O(n) extra space for std::unordered_map and recursive call stack. Here‘s an implementation in C which runs in O(n2) time.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of