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

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. • can someone explain how do I identify the root in this sequence? Like, I'm having a bit of trouble following the right search order here – Trey Sep 15 '19 at 18:28 • @Trey The sequence of nodes examined starts at the root of the tree, and you go left-right after comparing the search value with that of the current node. – Hendrik Jan Sep 18 '19 at 14:26 2 Answers 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$. • Awesome, that is a much easier approach. I was trying to complicate my life by testing the ranges between each node which confused me. – Squanchinator Dec 6 '17 at 0:27 • Using ranges can also be a solution. After seeing$925,202$in search of$363$you know you are in a subtree where all nodes belong to the interval$[202,925]$. Then you see$911$and you know the interval shrinks to$[202,911]\$. Etcetera. If you find a value outside the interval you know the sequences failed the requirements. – Hendrik Jan Dec 6 '17 at 14:03
• @HendrikJan your nice answer but some misunderstanding point. is it possible to add some step for details? – user355834 Sep 29 '20 at 5:52

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]$$