[Math] Construction of tree using inorder and postorder traversal

algorithmsdiscrete mathematicsgraph theorytrees

Consider the In-order and Post-order traversals of a tree as given below:

$\text{In-order: j e n k o p b f a c l g m d h i}$

$\text{Post-order: j n o p k e f b c l m g h i d a}$

The Pre-order traversal of the tree shall be:

  1. $\text{ a b f e j k n o p c d g l m h i}$
  2. $\text{ a b c d e f j k n o p g l m
    h i}$
  3. $\text{ a b e j k n o p f c d g l m h i }$
  4. $\text{j e n o p k f b c l m g
    h i d a}$

My attempt:

We assume that given inorder and postorder traversal of binary tree. So, construction of binary tree using inorder and postorder traversal:

enter image description here

So, preorder is : $\text{a b e j k n p o f d g l c m i h}$, but none option is matched. Somewhere answer key is given option $(3)$.

Can you explain it, please?

Best Answer

It appears to be an error in the answer key. I reconstruct the same tree and preorder that you do. I don’t even see any simple error, like a typo or a single small error in reconstructing the tree, that would explain the key’s answer.

Related Question