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?

- LASTIN = LASTPOST
- LASTIN = LASTPRE
- LASTPRE = LASTPOST
- None of the above

### 6 Comments

@vishalsharma539

**Complete Binary**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.**tree :****Perfect Binary****tree :****Almost complete binary**A almost complete binary tree is a binary tree which is complete binary tree but not perfect binary tree.**tree :**

## 2 Answers

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**).

### 15 Comments

@Arjun sir Can you please share an example of this question. Because below tree is Not Complete Binary Tree ; it is almost Complete Binary tree.

https://gateoverflow.in/?qa=blob&qa_blobid=6157632728430700751

LASTPRE will be from the second last level in case the complete binary tree is not full. So, choice (D).

LastIn should be from second lastindex in case last level is completely filled.LASTPRE will always be from last level.because if we are at second last level we process ROOT and then goto last level in pre order.Please check once?

@Arjun Sir please give example.. I think what u explained is true for Almost Complete Binary tree and not for complete binary tree. As per me, the answer to this question is same for Complete Binary Tree and Full Binary Tree

@Gate Keeda @rahul sharma 5 @sushmita

According to book of DS by* Thomas H. Cormen *

**For complete Binary tree **all levels should contain maximum nodes and

in if in last level nodes are available from left to right that is called** Nearly Completely Binary tree.**

In question it is mentioned as complete binary tree. So, isn't option **(B) **seems to be correct ?