Data Structures | Tree Traversals | Question 11

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? (GATE CS 2000)
(A) LASTIN = LASTPOST
(B) LASTIN = LASTPRE
(C) LASTPRE = LASTPOST
(D) None of the above

Answer: (D)
Explanation: 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. Thanks to Hunaif Muhammed for providing the correct explanation.

     1
   /    \
  2      3
 / \    /
4   5  6  

Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6 

Quiz of this Question