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