Which of the following can be a sequence of nodes examined in a binary search…

Concept

In a binary search tree, every node in a left subtree is smaller than its ancestor, and every node in a right subtree is larger than its ancestor.

During a search, each comparison narrows an active interval of permitted values. Every later node must lie inside all bounds established by the ancestors.

Application

1. Start at 190. Because 88 is less than 190, the next node must be in the left subtree, so the active range is (-infinity, 190); 60 lies in this range.

2. At 60, 88 is greater than 60, so move right. The range becomes (60, 190); 90 lies in this range.

3. At 90, 88 is less than 90, so move left. The range becomes (60, 90); 85 lies in this range.

4. At 85, 88 is greater than 85, so move right. The range becomes (85, 90); 88 lies in this range.

5. The search therefore reaches 88 through 190 → 60 → 90 → 85 → 88.

Contrast

• For 90 → 40 → 65 → 50 → 88, after 65 the lower bound is 65, but 50 is below that bound.

• For 90 → 110 → 80 → 85 → 88, after 90 the search for 88 must enter the left subtree, but 110 is greater than 90.

• For 65 → 140 → 80 → 70 → 88, after 80 the lower bound is 80, but 70 is below that bound.

Cross-check

A binary search tree containing this path can be constructed with 190 as the root, 60 as its left child, 90 as the right child of 60, 85 as the left child of 90, and 88 as the right child of 85. Its comparisons reproduce the same path, so the valid sequence is 190 → 60 → 90 → 85 → 88.