ITPEC FE Morning April 2019 Question 5

Binary Search Tree (BST) property — every node's left subtree contains only smaller values, and its right subtree contains only larger values.

Option (b) structure:
- Root 17 → left 14, right 19
- Node 14 → left 10, right 16
- Node 19 → left 18

Verification:
- 14 < 17 ✓, 19 > 17 ✓
- 10 < 14 ✓, 16 > 14 ✓ (and 16 < 17, so valid in left subtree of 17 ✓)
- 18 < 19 ✓ (and 18 > 17, so valid in right subtree of 17 ✓)

All BST constraints satisfied recursively.

Why not others:
- (a) Node 15 has right child 14 — but 14 < 15, so it cannot be in the right subtree
- (c) Node 16 has right child 14 — but 14 < 16, violates right-subtree rule
- (d) Root 20 has right child 19 — but 19 < 20, violates right-subtree rule

Key rule: In a BST, check the property recursively: every value in a left subtree must be less than the ancestor, and every value in a right subtree must be greater.

AI-generated — may contain errors