Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a post…

Concept

Each traversal has a fixed terminal vertex determined by its visiting rule. In postorder (left, right, root) the root is visited last, so LASTPOST is always the root. In inorder (left, root, right) the very last vertex is the one with no right descendant reached after exhausting all right branches — the rightmost vertex. In preorder (root, left, right) the last vertex is the deepest vertex of the rightmost path actually explored. “Always true” means the equality must hold for every complete binary tree, where the last level is filled from the left and may be only partially filled.

Application — trace a tree whose last level is partially filled

Take the 6-vertex complete binary tree (numbering vertices 1..6 by level, left to right): 1 is the root; 2 and 3 are its children; 4 and 5 are children of 2; 6 is the left child of 3.

1. Postorder visits 4, 5, 2, 6, 3, 1, so LASTPOST = 1 (the root).

2. Inorder visits 4, 2, 5, 1, 6, 3, so LASTIN = 3.

3. Preorder visits 1, 2, 4, 5, 3, 6, so LASTPRE = 6.

Cross-check each claimed equality

Test each offered equality against this single tree, where LASTPOST = 1, LASTIN = 3 and LASTPRE = 6:

• LASTIN = LASTPOST would need 3 = 1 — false here, because inorder ends at the rightmost vertex while postorder ends at the root.

• LASTPRE = LASTPOST would need 6 = 1 — false here, for the same root-versus-rightmost reason.

• LASTIN = LASTPRE would need 3 = 6 — false here: inorder's rightmost vertex (3) and preorder's last-explored vertex (6) differ in this tree, so this one counterexample is enough to show the equality does not hold for every complete binary tree.

Result

Because a complete binary tree may have a partially filled last level, every one of the three equalities can fail, so none of them is always true. The correct answer is “None of the above.”