Exercise 12.2.1

Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?

  1. 2, 252, 401, 398, 330, 344, 397, 363.
  2. 924, 220, 911, 244, 898, 258, 362, 363.
  3. 925, 202, 911, 240, 912, 245, 363.
  4. 2, 399, 387, 219, 266, 382, 381, 278, 363.
  5. 935, 278, 347, 621, 299, 392, 358, 363.

Each element of the sequence asserts something for the following elements, namely, that they are greater than it if it's smaller than the searched one, or smaller than it, if it is greater. E.g. in the first sequence, the first element asserts that the following are > 2, the second that it's following are > 252, the third that they are < 401 and so on. Thus:

The rest are valid.