ITPEC FE Morning April 2019 Question 5

The tree with root 17 — in a binary search tree every key in a node's left subtree is smaller than the node and every key in its right subtree is larger.

Check tree (b) node by node:

• •17: left subtree {14, 10, 16} all smaller, right subtree {19, 18} all larger
• •14: left 10 is smaller, right 16 is larger
• •19: left 18 is smaller (and still larger than 17, as the right subtree of 17 requires)

Every node passes, so an in-order traversal gives the sorted sequence 10, 14, 16, 17, 18, 19.

Answer (b)

Why not others:

• •(a) — 14 is the right child of 15, but 14 < 15, so it belongs on the left
• •(c) — 14 is the right child of 16, but 14 < 16
• •(d) — 19 is the right child of the root 20, but 19 < 20; the root's whole right subtree (19, 15, 16) is smaller than 20

Key rule: The ordering must hold against every ancestor, not only the parent; the quick test is that an in-order traversal of a binary search tree comes out sorted.

Algorithm and Programming · AI-written, may contain errors