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

@vishalsharma539

1. Complete Binary tree : A binary tree is complete if all level except possibly the last level is completely full, i.e last level may be or may not be full.
2. Perfect Binary tree : A complete binary tree in which last level is full.
3. Almost complete binary tree : A almost complete binary tree is a binary tree which is complete binary tree but not perfect binary tree.

---

I do not understand what is the meaning of Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively??

---

@Lakshman Patel RJIT

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

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

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 4

counter example for option B.