Suppose that we have numbers between 1 and 1000 in a binary search tree and we…

Key idea: When searching for 365 in a binary search tree, each visited node imposes a constraint on the possible values of later visited nodes. Maintain a running lower bound and upper bound for nodes on the path. If the current node is greater than 365 you go left and set the upper bound to that node; if it is less than 365 you go right and set the lower bound to that node. Every visited node must lie strictly between the current bounds.

• Sequence 4, 254, 403, 400, 332, 346, 399, 365 — Possible. Bounds evolve as: (−∞,+∞) → visit 4 → lower=4 → visit 254 → lower=254 → visit 403 → upper=403 → visit 400 → upper=400 → visit 332 → lower=332 → visit 346 → lower=346 → visit 399 → upper=399 → visit 365 which lies in (346,399).

• Sequence 926, 222, 913, 246, 900, 260, 364, 365 — Possible. Bounds: (−∞,+∞) → 926 (upper=926) → 222 (lower=222) → 913 (upper=913) → 246 (lower=246) → 900 (upper=900) → 260 (lower=260) → 364 (lower=364) → 365 in (364,900).

• Sequence 927, 204, 913, 242, 914, 247, 365 — Impossible. After 927 (upper=927), 204 (lower=204), 913 (upper=913), and 242 (lower=242), the allowed interval is (242,913). The next node 914 does not lie inside this interval (914 > 913), so it cannot appear on the search path for 365 in any BST.

• Sequence 4, 401, 389, 221, 268, 384, 383, 280, 365 — Possible. Bounds check: (−∞,+∞) → 4 (lower=4) → 401 (upper=401) → 389 (upper=389) → 221 (lower=221) → 268 (lower=268) → 384 (upper=384) → 383 (upper=383) → 280 (lower=280) → 365 in (280,383).

Conclusion: The only sequence that cannot be the nodes examined when searching for 365 is the sequence that contains 927, 204, 913, 242, 914, 247, 365, because 914 violates the running upper bound set earlier.