ITPEC FE Morning April 2018 Question 5

Tree (b), rooted at 17 — every key in each node's left subtree is smaller and every key in its right subtree is larger.

Checking tree (b):

• •17: left subtree {14, 10, 16} is all smaller, right subtree {19, 18} is all larger
• •14: left child 10 is smaller, right child 16 is larger (and still below 17)
• •19: left child 18 is smaller (and still above 17)

An in-order traversal (left, node, right) gives 10, 14, 16, 17, 18, 19, in ascending order, which is the test for a binary search tree.

Answer (b)

Why not others:

• •(a) — 14 is the right child of 15 but smaller than it; in-order gives 10, 15, 14, 16, 19
• •(c) — 14 is the right child of 16 but smaller than it; in-order gives 15, 16, 14, 18, 19, 20
• •(d) — the root 20 has 19 as its right child, and every key in the tree is below 20; this is a heap-like ordering (parent larger than children), not a search tree

Key rule: A binary tree is a search tree exactly when its in-order traversal is sorted; checking only each parent against its children can miss a violation against a higher ancestor.

Algorithm and Programming · AI-written, may contain errors