GATE IT 2008 | Question: 46

Question

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.

1. $MBCAFHPYK$
2. $KAMCBYPFH$
3. $MABCKYFPH$

Pick the true statement from the following.

• A. I and II are preorder and inorder sequences, respectively
• B. I and III are preorder and postorder sequences, respectively
• C. II is the inorder sequence, but nothing more can be said about the other two sequences
• D. II and III are the preorder and inorder sequences, respectively

Answer 1

In preorder, root comes at the beginning of the traversal sequence and in postorder, root comes at the last of the traversal sequence. So, out of the given sequences only $1$ and $2$ are having such kind of order i.e $K$ at the beginning and at the last.

Therefore, $2$ is the preorder and $1$ is postorder and the left sequence i.e $3$ will definitely be inorder.

So, option D is correct.

Comments

Adding little bit more to answer:-

For inorder:- left->root->right

For preorder:-root->left->right

Therefore for perorder and inorder the ending are same but it is for somecases

---

For complete binary tree which is not perfect this is not valid

---

@Walter_White how? can you elaborate it ?
 

---

iii. MABCKYFPH this inorder given in question is wrong !!

The correct Inorder comes out as MABCKFPHY if the tree comes out as given in this

https://gateoverflow.in/3356/gate-it-2008-question-46?show=71263#a71263

Answer 2

Using this as preorder KAMCBYPFH and inorder MABCKYFPH .

So this gives II and III are the preorder and inorder sequences, respectively.

Ans is option D

Answer 3

Answer: D

Binary Tree is:

    K                          
   /   \                          
  A    Y  
 /   \     \   
M  C    P           
     /     /  \
   B     F  H

Answer 4

The Problem-Solving Strategy

Never assume one of the options is true and start building. Instead, use the fundamental properties of traversals to deduce which sequence is which before you do any building.

Here is the simple, two-step logic:

 

Step 1: Find the Root

The root of the tree is the most important node. It has two very clear properties:

• It is the FIRST element in a Pre-order sequence.

• It is the LAST element in a Post-order sequence.

The root must be the same node. So, the "first element" of the Pre-order sequence must match the "last element" of the Post-order sequence.

Let's check the start/end of your three sequences:

• I: Starts with M, Ends with K

• II: Starts with K, Ends with H

• III: Starts with M, Ends with H

Now, find the matching pair:

• The start of II (K) matches the end of I (K).

• The start of I/III (M) doesn't match any end.

• The end of II/III (H) doesn't match any start.

This gives you a 100% certain deduction:

• The Root of the entire tree is K.

• Therefore, II is the Pre-order sequence.

• Therefore, I is the Post-order sequence.

 

Step 2: Identify In-order

By elimination, the only sequence left is III.

• III must be the In-order sequence.

The takeaway: Always use the "Root" property to identify the sequences before you start building. This turns a confusing guess-and-check problem into a simple logic puzzle.

Answer 5

1. Preorder (Root-Left-Right): Visit the root node first, then recursively do a preorder traversal of the left subtree, followed by the right subtree.
2. Inorder (Left-Root-Right): Recursively do an inorder traversal of the left subtree, visit the root node, then recursively do an inorder traversal of the right subtree.
3. Postorder (Left-Right-Root): Recursively do a postorder traversal of the left subtree, the right subtree, and finally visit the root node.

Option A: I and II are preorder and inorder sequences, respectively.
If the preorder sequence is I, and the inorder sequence is II, it should be possible to reconstruct a valid binary tree. Preorder gives the root first, and inorder gives the left and right subtrees around the root.
If this is true, the reconstructed tree must allow for a valid postorder traversal that matches III. If this does not align, the statement is false.

Option B: I and III are preorder and postorder sequences, respectively.
If I is the preorder sequence and III is the postorder sequence, then the first element of the preorder sequence (root) should match the last element of the postorder sequence (also root).
If they do not match, this statement is false.

Option C: II is the inorder sequence, but nothing more can be said about the other two sequences.
If we can conclusively determine that II is the inorder sequence but cannot identify the other sequences (preorder and postorder), this statement might hold.

Option D: II and III are the preorder and inorder sequences, respectively.
If II is the preorder sequence and III is the inorder sequence, we can reconstruct the binary tree.
This reconstruction produces a valid postorder sequence matching I, so this statement is true. 

So, option D is correct.