Binary Tree Traversal: Finding Postorder

We are given the inorder traversal ($d, b, e, a, f, c, g$) and preorder traversal ($a, b, d, e, c, f, g$) of a binary tree. We need to find the postorder traversal.

Reconstructing the Binary Tree

The process involves reconstructing the tree structure using the given traversals.

• Root Identification: The first element in the preorder traversal is the root of the tree. Here, the root is $a$.
• Inorder Partitioning: In the inorder traversal, elements to the left of the root form the left subtree, and elements to the right form the right subtree.
  • Inorder: $(d, b, e)$ | $a$ | $(f, c, g)$
  • Left subtree inorder: $d, b, e$
  • Right subtree inorder: $f, c, g$
• Preorder Partitioning: The elements immediately following the root in the preorder traversal belong to the left subtree, followed by the elements of the right subtree.
  • Preorder: $a$ | $(b, d, e)$ | $(c, f, g)$
  • Left subtree preorder: $b, d, e$
  • Right subtree preorder: $c, f, g$
• Recursive Construction: Repeat the process for the left and right subtrees.
  • Left Subtree (Rooted at 'b'):
    • Inorder: $d, b, e$
    • Preorder: $b, d, e$
    • Root is $b$.
    • Inorder partition: $(d)$ | $b$ | $(e)$
    • Left child: $d$ (Leaf node)
    • Right child: $e$ (Leaf node)
  • Right Subtree (Rooted at 'c'):
    • Inorder: $f, c, g$
    • Preorder: $c, f, g$
    • Root is $c$.
    • Inorder partition: $(f)$ | $c$ | $(g)$
    • Left child: $f$ (Leaf node)
    • Right child: $g$ (Leaf node)

The resulting tree structure has $a$ as the root, $b$ as its left child, and $c$ as its right child. $b$ has left child $d$ and right child $e$. $c$ has left child $f$ and right child $g$.

Generating Postorder Traversal

Postorder traversal follows the pattern: Left -> Right -> Root.

• Visit left subtree of $a$ (rooted at $b$):
  • Visit left subtree of $b$ (rooted at $d$):
    • $d$ (Leaf node) -> Output: $d$
  • Visit right subtree of $b$ (rooted at $e$):
    • $e$ (Leaf node) -> Output: $e$
  • Visit root $b$ -> Output: $b$
  • Left subtree postorder: $d, e, b$
• Visit right subtree of $a$ (rooted at $c$):
  • Visit left subtree of $c$ (rooted at $f$):
    • $f$ (Leaf node) -> Output: $f$
  • Visit right subtree of $c$ (rooted at $g$):
    • $g$ (Leaf node) -> Output: $g$
  • Visit root $c$ -> Output: $c$
  • Right subtree postorder: $f, g, c$
• Visit root $a$ -> Output: $a$

Combining the results gives the final postorder traversal: $d, e, b, f, g, c, a$.