ITPEC FE Morning October 2020 Question 6

The tree with root 4 — every node's left subtree holds smaller values and its right subtree larger ones, so an in-order walk gives 1 to 9 in order.

In a binary search tree, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. An equivalent test: an in-order traversal (left, node, right) must visit the values in ascending order.

• •(b): 4 has left subtree 2 (1, 3) and right subtree 8 (6 (5, 7), 9); in-order gives 1, 2, 3, 4, 5, 6, 7, 8, 9

Answer (b)

Why not others:

• •(a) — 2 is the left child of the root 1 but is larger than it; in-order gives 4, 2, 5, 1, …
• •(c) — 5 is the right child of 6 but is smaller than it, and 3, 1, 2 sit in the right subtree of the root 7 although they are smaller than 7
• •(d) — 8 is the right child of the root 9 but is smaller than it

Key rule: The ordering must hold for whole subtrees, not just parent and child; an in-order traversal that comes out sorted checks every node at once.

Algorithm and Programming · AI-written, may contain errors