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