ITPEC FE Morning April 2018 Question 5
ITPEC FE Morning April 2018 — Question 5 of 80
Binary Search Tree (BST) validation — identify a correctly structured BST where every node satisfies the BST property.
BST rule: For every node, all values in the left subtree must be less than the node, and all values in the right subtree must be greater than the node. This must hold globally, not just for immediate children.
Checking option (b):
- Root 17 → left child 14 (14 < 17 ✓), right child 19 (19 > 17 ✓)
- Node 14 → left child 10 (10 < 14 ✓, also 10 < 17 ✓), right child 16 (16 > 14 ✓, also 16 < 17 ✓)
- Node 19 → left child 18 (18 < 19 ✓, also 18 > 17 ✓)
- All nodes satisfy the BST property globally. ✅
Why not others:
- (a) Node 15 has right child 14, but 14 < 15 — right child must be greater. Violates BST property.
- (c) Node 16 has right child 14, but 14 < 16 — right child must be greater. Violates BST property.
- (d) Root 20 has right child 19, but 19 < 20 — right subtree values must be greater than root. Also, node 19 has right child 16, and 16 < 19. Violates BST property.
Key rule: Always check the BST property globally — a node must satisfy constraints from all ancestors, not just its immediate parent.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.