ITPEC FE Morning April 2023 Question 7

Pre-order Tree Traversal — visit root, then left subtree, then right subtree (NLR).

Given BST with root 9:

• •Visit 9 → left subtree rooted at 3
• •Visit 3 → left child 1
• •Visit 1 (leaf) → back to 3, right child 6
• •Visit 6 → left child 4
• •Visit 4 (leaf) → right child 7
• •Visit 7 (leaf) → back to 9, right subtree rooted at 10
• •Visit 10 → left child 14
• •Visit 14 → left child 13
• •Visit 13 (leaf)

Result: 9, 3, 1, 6, 4, 7, 10, 14, 13

Why not others:
- (a) 1, 3, 4, 6, 7, 9, 10, 13, 14 — this is in-order traversal (LNR, sorted BST output)
- (b) 1, 4, 7, 6, 3, 13, 14, 10, 9 — this is post-order traversal (LRN)
- (d) 9, 3, 10, 1, 6, 14, 4, 7, 13 — this is level-order traversal (BFS, layer by layer)

Key rule: Pre-order = NLR (Node, Left, Right). Always process root before children.

AI-generated — may contain errors