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

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


 

For example, consider below tree:

Binary Tree


Input: 

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

 
Output:

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

 
We start with the root node whose value would be the last item in the postorder sequence. The idea is to find boundaries of the left and right subtree of root node in the given 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 preorder traversal of the tree. This is demonstrated below in C++ –

 

Download   Run Code

Output:

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

 
The time complexity of above solution is O(n) and requires O(n) extra space for std::unordered_map, std::stack, and recursive call stack.

 
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