ITPEC FE Morning October 2020 Question 6

Binary Search Tree (BST) identification — check the BST property for every node.

BST rule: for each node, all values in the left subtree are less, and all values in the right subtree are greater.

Check each option:

• •(a) Root 1 → right child 3 → left child 6 — 6 > 3 violates BST property ✗
• •(b) Root 4 → left subtree 2(1,3), right subtree 8(6(5,7), 9) — every node satisfies the rule ✓
• •(c) Node 8 → left child 3 → right child 2 — 2 < 3 in the right subtree violates BST ✗
• •(d) Root 9 → right child 8 → right child 6 — 6 < 8 in the right subtree violates BST ✗

Why not others:
- (a) 6 placed as left child of 3 breaks the "left < parent" rule
- (c) 2 placed as right child of 3 must be greater than 3
- (d) 6 placed as right child of 8 must be greater than 8

Key rule: check the BST property at every node, not just the root — a common trap is only checking parent-child pairs without verifying the entire subtree constraint.

AI-generated — may contain errors