Let LASTPOST, LASTIN, and LASTPRE denote the last vertex visited in postorder,…
2000
Let LASTPOST, LASTIN, and LASTPRE denote the last vertex visited in 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
Attempted by 41 students.
Show answer & explanation
Correct answer: D
Use the following complete binary tree as a counterexample:
A
/ \
B C
/ \ /
D E FInorder: D B E A F C, so LASTIN = C.
Postorder: D E B F C A, so LASTPOST = A.
Preorder: A B D E C F, so LASTPRE = F.
Thus LASTIN ≠ LASTPOST, LASTIN ≠ LASTPRE, and LASTPRE ≠ LASTPOST. Therefore none of the first three statements is always true.
Correct answer: None of the above