-
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 these
- LASTIN = LASTPOST
Correct Option: D
It is given that the given tree is complete binary tree. For a complete binary tree, the last visited node will always be same for inorder and preorder traversal. None of the above is true even for a complete binary tree. The option (a) is incorrect because the last node visited in Inorder traversal is right child and last node visited in Postorder traversal is root.
The option (c) is incorrect because the last node visited in Preorder traversal is right child and last node visited in Postorder traversal is root.
For option (b), see the following counter example.
Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6
So, lastpost = 1, lastpre = 6, lastin = 3.
Hence option (d) is correct.
