3
$\begingroup$

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.

$\endgroup$

This question has an open bounty worth +50 reputation from Trey ending in 16 hours.

The current answers do not contain enough detail.

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

  • $\begingroup$ 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 $\endgroup$ – Trey Sep 15 at 18:28
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Sep 18 at 14:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Awesome, that is a much easier approach. I was trying to complicate my life by testing the ranges between each node which confused me. $\endgroup$ – Squanchinator Dec 6 '17 at 0:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Dec 6 '17 at 14:03
0
$\begingroup$

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

New contributor
tanmay_freak is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.