How to Print the Postorder Traversal of a Binary Tree Given the Preorder and Inorder Traversals?

Question

I was given a task of trying to print the postorder traversal of a binary tree when you are given the preorder and the inorder traversals.

I went online to search up the problem, but the only results that I found was this GeekForGeeks article. However, I found this article quite confusing and I didn't understand how to solve this problem even after reading the article. Can someone help simplify the article into simpler words? Thanks!

Answer 1

This is impossible in the general case. Consider:

  A
A   B

Let's label these as

  1
2   3

• Preorder traversal AAB (1, 2, 3)
• Inorder traversal AAB (2, 1, 3)
• Postorder traversal ABA (2, 3, 1)

Now consider:

A (1)
  A (2)
    B (3)

• Preorder: AAB (1, 2, 3)
• Inorder: AAB (1, 2, 3)
• Postorder: BAA (3, 2, 1)

Given preorder and inorder trees as AAB will not have an unambigous postorder representation.