2
$\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$
1
$\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
  • $\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

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.