Question

When inorder traversing a tree resulted in ABCDEGFHI and postorder traversing the tree resulted in ACBEFGIHD; the preorder traversal would return:

• A. DBCAGEHIF
• B. DBACHGEFI
• C. DCBAGEFHI
• D. IDBACGEHF

Hint:

Preorder traversal visits root first, followed by the left subtree, and then the right subtree.

Answer 1

The Correct Option is A

Step 1: Understanding Tree Traversals
- Inorder (LNR): Left subtree → Node → Right subtree \[ ABCDEGFHI \] - Postorder (LRN): Left subtree → Right subtree → Node \[ ACBEFGIHD \] - Preorder (NLR): Node → Left subtree → Right subtree
- The goal is to determine the preorder traversal.
Step 2: Reconstructing the Binary Tree From postorder traversal, the last node is the root: \[ D \text{ (Root)} \] Breaking postorder into left and right subtrees:
- Left subtree: ACBE
- Right subtree: FGIH
From inorder, left subtree (ABCDE) and right subtree (GFHI) confirm the structure.
Step 3: Determining Preorder (Root → Left → Right) From the constructed tree: \[ DBCAGEHIF \]
Step 4: Evaluating the Options
- (A) Correct: Matches the derived preorder traversal.
- (B) Incorrect: Incorrect order of subtree traversal.
- (C) Incorrect: Wrong placement of nodes.
- (D) Incorrect: Wrong root placement.