GATE2000-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

• A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. 
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 

---

if this is complete then, what is almost complete...?

---

actually various textbook follows different definition of complete and full binary tree ,

---

@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??

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

I guess this is also a Complete Binary Tree. And the question has asked for the condition which is always true. In some cases what you said may not be true as the above one.

---

yeah right thanks !!!

---

Yes. You are correct. I took "full" instead of "complete".

---

Arjun Sir, Can you please explain the difference between full and complete binary tree as different sources have different binary trees

---

Please update this answer.

---

This is copied from Rosen, and the defiition of complete Binary Tree is different than yours.
the tree which you are calling as Full is same as Complete tree.
answer should be (B), right?

---

As far as I know, if the definition is not mentioned, then a complete binary tree is one in which nodes are present sequentially(i.e. following the property of Almost Complete Binary tree) and a node can have either 0 or 2 children. A node should'nt have just a single child thus !!

---

@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

---

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This is 100% correct.

---

@Arjun sir,In answer you mentioned that :-

 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?

---

This tree is almost complete binary tree because almost complete binary tree means leave should be present at last level and last but one level.

---

Will it 'B' for full binary Tree?

---

@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 ?

Answer 2

The answer is D.

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

Comments

dont you think it should be (B) ?

---

Look at my comment below for explanation.

---

always true for full binary tree ..but not for complete !

---

Yes for full binary tree it is option B

---

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