ITPEC FE Morning October 2021 Question 8

Binary search tree — for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger.

Check each node with children: 5 has 1–4 on the left and 6–10 on the right; 3 has 2 and 1 on the left and 4 on the right; 2 has 1 on the left; 7 has 6 on the left and 8–10 on the right; 9 has 8 on the left and 10 on the right. An in-order walk visits 1, 2, 3, …, 10 in sorted order, which confirms it.

Answer (b)

Why not others:

• •(a) Balanced tree — describes shape, not the key order the figure is built on; in the strict sense of a tree whose leaves all sit on one level (as in a B-tree) it also fails, since leaves 4 and 6 are one level above leaves 1, 8 and 10
• •(c) Max heap — every parent would have to be at least as large as its children, but root 5 is smaller than its child 7
• •(d) Min heap — every parent would have to be no larger than its children, but root 5 is larger than its child 3

Key rule: A heap orders each parent against its children, so the root is the extreme; a binary search tree orders left against right, so an in-order walk is sorted.

Algorithm and Programming · AI-written, may contain errors