1
00:00:00,610 --> 00:00:01,950
Hello, everyone, and welcome back.

2
00:00:02,620 --> 00:00:09,250
In the previous lesson, I challenge you to try and figure out what boundry to add to every single value

3
00:00:09,250 --> 00:00:14,080
so that recursive function works in the sense that it receives both a greater than a lesser than value,

4
00:00:14,200 --> 00:00:19,330
regardless of where and which direction the traversal is made inside of our tree.

5
00:00:20,310 --> 00:00:25,680
So here, let's think about this route value to the seven, because we're missing this boundary.

6
00:00:26,490 --> 00:00:36,240
We know that whenever we go left, we want to persist some value for what it must be greater than here

7
00:00:36,240 --> 00:00:37,400
when we make this step.

8
00:00:37,410 --> 00:00:40,560
We don't care at this point what it's greater than.

9
00:00:40,560 --> 00:00:42,570
The only condition is that it's less than 12.

10
00:00:42,720 --> 00:00:44,550
It can be greater than anything.

11
00:00:45,150 --> 00:00:46,870
But as long as it's less than 12, it's valid.

12
00:00:47,190 --> 00:00:52,100
So you might think, what if I just picked a small value like negative ten thousand, for example?

13
00:00:52,710 --> 00:00:57,120
So as long as this value is greater than negative at ten thousand, then this works.

14
00:00:57,480 --> 00:01:00,940
And as we see whenever we go left, we persist the greater than value.

15
00:01:00,990 --> 00:01:04,650
So here we're still passing the greater than negative ten thousand.

16
00:01:05,340 --> 00:01:06,710
And so far it still works.

17
00:01:07,290 --> 00:01:10,980
But remember, we have no idea how far down this branch goes.

18
00:01:11,160 --> 00:01:16,770
And let's say down here there was a negative one hundred thousand or negative a million value.

19
00:01:17,580 --> 00:01:23,460
When we do our traversal or traversal is still going to try and say that it's within this boundary of

20
00:01:23,460 --> 00:01:31,260
negative ten thousand here when it tries to say if this value that we're moving to the left is greater

21
00:01:31,260 --> 00:01:31,920
than negative.

22
00:01:31,920 --> 00:01:38,250
Ten thousand but lesser than seven here, it's going to fail because negative one hundred thousand is

23
00:01:38,250 --> 00:01:42,800
lesser than ten thousand, but it must be greater than 10K according to our rule.

24
00:01:43,020 --> 00:01:46,530
So here we see that this is indeed valid.

25
00:01:46,530 --> 00:01:50,760
It's perfectly valid for this value to be here, but our rule does not work.

26
00:01:51,360 --> 00:02:00,030
This value that we want to say at this point must be infinitesimally small and the value that is actually

27
00:02:00,030 --> 00:02:03,150
infinitesimally small is negative infinity.

28
00:02:03,750 --> 00:02:10,350
So here we can actually say that when we start traversing to the left for the first time, that this

29
00:02:10,350 --> 00:02:13,710
value must be greater than negative infinity by less than 12.

30
00:02:14,070 --> 00:02:18,060
If we traverse left again, we're keeping this greater than negative infinity.

31
00:02:19,540 --> 00:02:27,070
And this is still valid, and no matter how far down we go, every value is going to be greater than

32
00:02:27,070 --> 00:02:28,030
negative infinity.

33
00:02:28,690 --> 00:02:33,250
The moment that we make a change, though, that's where it starts to get interesting, because the

34
00:02:33,250 --> 00:02:36,150
moment we go right, we want to replace this value now.

35
00:02:36,400 --> 00:02:43,270
And that makes sense because all we're saying is that when we go right, if the current value is greater,

36
00:02:43,270 --> 00:02:50,050
then the value of negative infinity, that this next value must be greater, then updated because this

37
00:02:50,050 --> 00:02:56,170
value is obviously going to be greater than negative infinity, which means that nine being greater

38
00:02:56,170 --> 00:03:01,120
than negative infinity is not meaningful, but nine being greater than seven is meaningful because that's

39
00:03:01,120 --> 00:03:02,620
the condition we need to satisfy.

40
00:03:03,190 --> 00:03:11,470
So what we see is that whenever we go right, we're updating this greater than value if the value that

41
00:03:11,470 --> 00:03:17,590
we're updating is greater than the previous value that we use to compare for greater than.

42
00:03:17,920 --> 00:03:19,450
So here we're going right again.

43
00:03:19,810 --> 00:03:24,540
We see that the current value of nine is greater than our previous greater than value of seven.

44
00:03:24,580 --> 00:03:26,850
So we update it accordingly.

45
00:03:27,400 --> 00:03:29,140
So here we figured out a rule.

46
00:03:29,440 --> 00:03:35,620
If we go left, keep the previous value that we are greater than if we go right.

47
00:03:36,160 --> 00:03:41,050
Update the value of the greater then to the current node's value.

48
00:03:41,380 --> 00:03:45,150
If we're going left, don't keep the fact that it's greater than negative infinity.

49
00:03:45,430 --> 00:03:51,000
We know for sure going right that this value must be greater than the previous value we had as our condition.

50
00:03:51,340 --> 00:03:53,650
So update it to the current node's value.

51
00:03:54,040 --> 00:03:55,450
So this is what we've seen.

52
00:03:55,840 --> 00:03:58,300
If we go left, keep the greater than value.

53
00:03:58,330 --> 00:04:01,300
If we go right, update it to our current value.

54
00:04:01,960 --> 00:04:08,200
So now we've figured out what to do with our greater than value, regardless of which direction we're

55
00:04:08,200 --> 00:04:08,880
traversing.

56
00:04:09,310 --> 00:04:10,920
But what about our lesser than value?

57
00:04:11,110 --> 00:04:12,020
Let's figure this out.

58
00:04:12,460 --> 00:04:13,780
So starting from the route, let's go.

59
00:04:13,780 --> 00:04:14,190
Right.

60
00:04:14,620 --> 00:04:19,380
We know that going REITs are lesser than value updates to our current node value.

61
00:04:19,600 --> 00:04:25,210
This stays the exact same, but this must now be lesser than some value.

62
00:04:25,210 --> 00:04:30,760
And for us, we know that if we're going to use negative infinity for greater than let's use positive

63
00:04:30,760 --> 00:04:37,210
infinity for our lesser, then similarly, if we go right again, we know that we're updating our greater

64
00:04:37,210 --> 00:04:38,590
than value to our current node.

65
00:04:38,890 --> 00:04:43,560
So we're updating it to 18, but we're keeping the lesser than value here.

66
00:04:44,440 --> 00:04:47,470
So as long as this value is lesser than infinity, this is correct.

67
00:04:48,240 --> 00:04:54,600
But what about if we were to go left and say that if we go left, we see now that we need to update

68
00:04:54,600 --> 00:04:57,060
the lesser than value to the current node's value?

69
00:04:57,090 --> 00:04:59,430
We don't keep the infinity.

70
00:04:59,970 --> 00:05:07,350
And this makes sense because if we're going left, we know that this node must now be the new placement

71
00:05:07,350 --> 00:05:13,050
of the value that we expect this value to be lesser than if it's the left.

72
00:05:13,050 --> 00:05:14,310
That's literally the condition.

73
00:05:14,520 --> 00:05:18,490
The node to the left of our node must be lesser than my nodes value.

74
00:05:18,540 --> 00:05:22,580
So that's why we update this new lesser than value to the current nodes value.

75
00:05:23,040 --> 00:05:28,470
But we can keep the previous greater than value as long as we're going left.

76
00:05:28,890 --> 00:05:34,140
So here we figured out our relationship and what we noticed is that when we start, we're going to have

77
00:05:34,140 --> 00:05:35,410
to start from the root as well.

78
00:05:35,850 --> 00:05:41,130
So what's the boundary for this condition while maintaining what we pass to the left and the right while

79
00:05:41,130 --> 00:05:44,640
it's going to be the exact same thing, but combined.

80
00:05:44,790 --> 00:05:51,630
So as long as this root value is greater than negative infinity, but less so than infinity, it's valid,

81
00:05:51,630 --> 00:05:52,230
which is true.

82
00:05:52,230 --> 00:05:53,490
Our value can be anything.

83
00:05:53,520 --> 00:05:54,720
So this condition makes sense.

84
00:05:55,020 --> 00:06:01,500
When you go left, though, you want to replace the lesser than value, as we've established with 12

85
00:06:01,530 --> 00:06:02,610
instead of infinity.

86
00:06:03,300 --> 00:06:10,380
When you go right, you want to update the greater than value with twelve instead of negative infinity,

87
00:06:10,710 --> 00:06:14,440
and then the rules will just persist throughout the rest of this code.

88
00:06:15,180 --> 00:06:17,270
So here is my challenge to you.

89
00:06:17,610 --> 00:06:23,820
Take what we've just made, really understand how we came to this conclusion by walking through this

90
00:06:23,820 --> 00:06:29,630
and figuring out what it is that we were missing at every step and trying to hold out this solution.

91
00:06:29,970 --> 00:06:35,460
It's actually pretty straightforward, but getting to it was quite complicated because we had to think

92
00:06:35,460 --> 00:06:43,020
of a way to use a recursive reusable bit of logic on every traversal in order for this to be properly

93
00:06:43,020 --> 00:06:43,440
valid.

94
00:06:43,620 --> 00:06:48,420
And we have to think about all the different ways that we could step through this tree in order to come

95
00:06:48,420 --> 00:06:49,610
up with this solution.

96
00:06:50,190 --> 00:06:52,770
So try and cut it out and I'll show you how to do it in the next video.