patternMinor
Which of the following sequences could not be the sequences of nodes examined in a binary search tree?
Viewed 0 times
nodesthesearchcouldexaminedfollowingbinarywhichnotsequences
Problem
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
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.
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, 363I 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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#84996, answer score: 2
Revisions (0)
No revisions yet.