Which of the following sequences could not be the sequences of nodes examined in a binary search tree?

Question

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

a) 924,220,911,244,898,258,362,363$

b) 925,202,911,240,912,245,363

c) 2,399,387,219,266,382,381,278,363

d) 935,278,347,621,299,392,358,363

e) 925, 202, 911, 240, 912, 245, 363

I know that $d$ and $e$ are not valid sequences, my professor told us so. I know it has something to do the range between jumping from node to node, which has something to do with the following property of BST's

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

I just don't see it, been trying to simulate the path sequence with no clear breakthrough.

Answer 1

Actually the test is quite easy. If you consider the subsequence of numbers greater than the final number $363$, this sequence is supposed to decrease.

Thus, in the case of $e: 925, 202, 911, 240, 912, 245, 363$, the subsequence is $925, 911, 912, 363$ and we see the problem.

Why is that so? If we see a number $x$ larger than the target $363$, we are supposed to move to the left subtree of $x$ where all numbers will be smaller than $x$. Thus also all numbers we will see from there will be smaller. As a consequence the numbers larger than $363$ will decrease.

Similarly, the numbers smaller than $363$ will increase. That is why $d$ fails: $278,347,299,358,363$.

Answer 2

I know this is old but in response of @Trey here's the analysis.

We know that in BST you either go to left Subtree$(target > root)$ or Right Subtree $(target < root)$. In this process you can say that you will only search values between two ranges that depends on which path you want to proceed.

Here is a short Algorithm to describe it:

Let CurrentNode be the root and target is the element you want to find.

1. Initialize MaxValue= INT_MAX, MinValue=INT_MIN.
2. CurrentNode->value should be within [MinValue,MaxValue]. If not then it's not BST.
3. If CurrentNode->value == target you return it.
4. Else if CurrentNode->value > target we go to left subtree and update MaxValue = CurrentNode->value.
5. Else CurrentNode->value < target we go to right subtree and update MinValue = CurrentNode->value

Let's convert this algorithm to array of elements (sequence given can be seen as array of elements):

1. Initialize MaxValue= INT_MAX, MinValue=INT_MIN.

2. For each element in sequence :

   a. CurrentElement should be within [MinValue,MaxValue]. If not then it's not a valid sequence.

   b. If CurrentElement == target you it is a valid sequence and end the algorithm.

   c. Else if CurrentElement > NextElement (we go to left subtree) so update MaxValue = CurrentElement.

   d. Else if CurrentElement < NextElement (we go to right subtree) so update MinValue = CurrentElement

Let's run it on $1$ wrong case : $[ 925, 202, 911, 240, 912, 245, 363]$

$Initialize Range = [-65535,35535]$ $1. target = 363 , CurrentElement = 925 , NextElement = 202, Range=[-65535 , 65535]$

Here $CurrentElement > NextElement =>$ go left $=> Range = [-65535,925]$

$2. target = 363 , CurrentElement = 202 , NextElement = 911, Range=[-65535 , 925]$

Here $CurrentElement < NextElement =>$ go right $=> Range = [202,925]$

$3. target = 363 , CurrentElement = 911 , NextElement = 240, Range=[202 , 925]$

Here $CurrentElement > NextElement =>$ go left $=> Range = [202,911]$

$4. target = 363 , CurrentElement = 240 , NextElement = 912, Range=[202,911]$

Stop as $CurrentElement$ is outside $=> Range = [202,911]$