Hello, everyone, and welcome back.
In the previous lesson, I challenge you to try and figure out what boundry to add to every single value
so that recursive function works in the sense that it receives both a greater than a lesser than value,
regardless of where and which direction the traversal is made inside of our tree.
So here, let's think about this route value to the seven, because we're missing this boundary.
We know that whenever we go left, we want to persist some value for what it must be greater than here
when we make this step.
We don't care at this point what it's greater than.
The only condition is that it's less than 12.
It can be greater than anything.
But as long as it's less than 12, it's valid.
So you might think, what if I just picked a small value like negative ten thousand, for example?
So as long as this value is greater than negative at ten thousand, then this works.
And as we see whenever we go left, we persist the greater than value.
So here we're still passing the greater than negative ten thousand.
And so far it still works.
But remember, we have no idea how far down this branch goes.
And let's say down here there was a negative one hundred thousand or negative a million value.
When we do our traversal or traversal is still going to try and say that it's within this boundary of
negative ten thousand here when it tries to say if this value that we're moving to the left is greater
than negative.
Ten thousand but lesser than seven here, it's going to fail because negative one hundred thousand is
lesser than ten thousand, but it must be greater than 10K according to our rule.
So here we see that this is indeed valid.
It's perfectly valid for this value to be here, but our rule does not work.
This value that we want to say at this point must be infinitesimally small and the value that is actually
infinitesimally small is negative infinity.
So here we can actually say that when we start traversing to the left for the first time, that this
value must be greater than negative infinity by less than 12.
If we traverse left again, we're keeping this greater than negative infinity.
And this is still valid, and no matter how far down we go, every value is going to be greater than
negative infinity.
The moment that we make a change, though, that's where it starts to get interesting, because the
moment we go right, we want to replace this value now.
And that makes sense because all we're saying is that when we go right, if the current value is greater,
then the value of negative infinity, that this next value must be greater, then updated because this
value is obviously going to be greater than negative infinity, which means that nine being greater
than negative infinity is not meaningful, but nine being greater than seven is meaningful because that's
the condition we need to satisfy.
So what we see is that whenever we go right, we're updating this greater than value if the value that
we're updating is greater than the previous value that we use to compare for greater than.
So here we're going right again.
We see that the current value of nine is greater than our previous greater than value of seven.
So we update it accordingly.
So here we figured out a rule.
If we go left, keep the previous value that we are greater than if we go right.
Update the value of the greater then to the current node's value.
If we're going left, don't keep the fact that it's greater than negative infinity.
We know for sure going right that this value must be greater than the previous value we had as our condition.
So update it to the current node's value.
So this is what we've seen.
If we go left, keep the greater than value.
If we go right, update it to our current value.
So now we've figured out what to do with our greater than value, regardless of which direction we're
traversing.
But what about our lesser than value?
Let's figure this out.
So starting from the route, let's go.
Right.
We know that going REITs are lesser than value updates to our current node value.
This stays the exact same, but this must now be lesser than some value.
And for us, we know that if we're going to use negative infinity for greater than let's use positive
infinity for our lesser, then similarly, if we go right again, we know that we're updating our greater
than value to our current node.
So we're updating it to 18, but we're keeping the lesser than value here.
So as long as this value is lesser than infinity, this is correct.
But what about if we were to go left and say that if we go left, we see now that we need to update
the lesser than value to the current node's value?
We don't keep the infinity.
And this makes sense because if we're going left, we know that this node must now be the new placement
of the value that we expect this value to be lesser than if it's the left.
That's literally the condition.
The node to the left of our node must be lesser than my nodes value.
So that's why we update this new lesser than value to the current nodes value.
But we can keep the previous greater than value as long as we're going left.
So here we figured out our relationship and what we noticed is that when we start, we're going to have
to start from the root as well.
So what's the boundary for this condition while maintaining what we pass to the left and the right while
it's going to be the exact same thing, but combined.
So as long as this root value is greater than negative infinity, but less so than infinity, it's valid,
which is true.
Our value can be anything.
So this condition makes sense.
When you go left, though, you want to replace the lesser than value, as we've established with 12
instead of infinity.
When you go right, you want to update the greater than value with twelve instead of negative infinity,
and then the rules will just persist throughout the rest of this code.
So here is my challenge to you.
Take what we've just made, really understand how we came to this conclusion by walking through this
and figuring out what it is that we were missing at every step and trying to hold out this solution.
It's actually pretty straightforward, but getting to it was quite complicated because we had to think
of a way to use a recursive reusable bit of logic on every traversal in order for this to be properly
valid.
And we have to think about all the different ways that we could step through this tree in order to come
up with this solution.
So try and cut it out and I'll show you how to do it in the next video.