GATE CSE 2000 | Question: 2.16

Question

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true?

• A. LASTIN = LASTPOST
• B. LASTIN = LASTPRE
• C. LASTPRE = LASTPOST
• D. None of the above

Comments

@Lakshman Patel RJIT

It is nothing but just simple preorder, postorder, inorder traversal.

---

       3

      /

    2

Inorder = 2, 3

Preorder = 3, 2

∴ LASTIN ≠ LASTPRE

---

https://www.geeksforgeeks.org/dsa/difference-between-full-and-complete-binary-tree/

Answer 1

Inorder : Left $\rightarrow$ Root $\rightarrow$ Right

Preorder : Root $\rightarrow$ Left $\rightarrow$ Right

Postorder: Left $\rightarrow$ Right $\rightarrow$ Root

If the binary tree is full (last level is fully filled), the last visited node in Inorder and Preorder must be the rightmost one in the last level. But for a complete binary tree this need not be the case (in a complete binary tree last level need not be fully filled) and LASTPRE will be from the second last level in case the complete binary tree is not full. So, choice (D).

Comments

@Abhisek Tiwari 

 

Will it 'B' for full binary Tree?

Yes, absolutely why it can’t be... 

because every time you make the inorder and preorder traversal you will get the …

LASTIN = LASTPRE

---

@Gate Keeda I think that depends. E.g. if you take this complete binary tree, then you'll get both LASTIN and LASTPRE as 7. So taking an examples is probably not the best way to address this question.  

---

@Arjun sir, I believe you mean to say LASTIN will be from second last level.As in that case LASTPRE will from last and LASTIN from second last.

Answer 2

The answer is D.

Take any random sequence and check for the inorder, postorder and preorder Last Node.

Comments

Here, you have to be careful. It Says, "Complete binary tree" for which every level except last is completely filled and at last level, nodes are as far as left possible.

---

i am getting B as answer ..i take a perfect complete binary tree then the last of inorder and last of preorder is same.

---

@Shubham

That will be same if the root contains both left and right child, but what if it doesn't ?

Read above comment by Gate Keeda

Answer 3

counter example for option B.

Answer 4

Answer: D. None of the above

We begin with a simple binary tree:

    A
   / \
  B   C

Preorder	Root Left Right A B C	⇒ LASTPRE = C
Inorder	Left Root Right B A C	⇒ LASTIN = C
Postorder	Left Right Root B C A	⇒ LASTPOST = A

At this point, we observe that \( \text{LAST}{\text{IN}} = \text{LAST}{\text{PRE}} \).

Both Preorder and Inorder traversals typically end in the Right subtree. But if the tree lacks a right child, the equality no longer holds.

Consider:

 A
/
B

Preorder	Root Left Right A B	⇒ LASTPRE = B
Inorder	Left Root Right B A	⇒ LASTIN = A

\(\Rightarrow \text{LAST}{\text{IN}} \ne \text{LAST}{\text{PRE}}\)

---

🔽 Show another example (counterexample)

This is not the only example. If you notice, both sequences typically end with the Right subtree. The moment the last node in the tree does not have a right child, it serves as a counterexample.

      A
     / \
    B   C
   / \  /
  X   Y D

Preorder	Root Left Right A B X Y C D	⇒ LASTPRE = D
Inorder	Left Root Right X B Y A D C	⇒ LASTIN = C
Postorder	Left Right Root X Y B D C A	⇒ LASTPOST = A

Now, \( \text{LAST}_{\text{IN}} \ne \text{LAST}_{\text{PRE}} \). The equality no longer holds because the Preorder traversal continues inside \( C \)’s subtree, whereas the Inorder traversal ends at \( C \).

Therefore, none of the equalities (A, B, or C) always hold for general binary trees.

✅ D. None of the above

Answer 5

REVERSE APPROACH !!

Consider a Complete Binary Tree with only 1 node, say A,

Then its PREORDER = POSTORDER = INORDER = A

Therefore, only Option D matches (as Question ask, which always TRUE)

Answer 6

Take a height 2 (root at 0) CBT, fill everything except the last node's last leaf, calculate in, pre and post orders, none of them match, now remove the last parent's one leaf too, now in and pre orders match, the key is to identify that they don't always match