ITPEC FE Subject B April 2024 Question 9

Preorder binary tree traversal using an explicit stack.

The procedure performs a preorder traversal (root → left → right) of a binary tree using a stack (LIFO). Since the array index starts at 1, the stack pointer sp begins at 1 after pushing the root.

Blank A — loop condition (`sp is not 0`):
- sp = 1 means one element on the stack. After popping (sp ← sp - 1), sp becomes 0, meaning the stack is empty.
- The loop should continue while the stack is not empty, i.e., sp is not 0.

Blanks B and C — push order matters (LIFO):
- For preorder, after visiting the current node, we need to process left child first, then right.
- Since a stack is LIFO, we must push right first, then left — so left ends up on top and gets popped next.
- First if checks and pushes B = `v.right` (pushed first → deeper in stack).
- Second if checks and pushes C = `v.left` (pushed second → on top → popped first).

Why not others:
- (a) A=0, B=v.left, C=v.right — pushes left first, right on top → processes right before left (incorrect order)
- (c) A=-1 — with 1-based indexing, empty stack means sp = 0, not -1
- (d) A=-1 — same issue with the loop condition; -1 would cause an out-of-bounds access

Key rule: In a stack-based preorder traversal, push the right child before the left child so that LIFO order produces root → left → right.

AI-generated — may contain errors