1
00:00:00,600 --> 00:00:02,130
Hello, everyone, and welcome back.

2
00:00:02,520 --> 00:00:08,850
In the previous lesson, I challenge you to try and figure out what boundary to add to every single

3
00:00:08,850 --> 00:00:13,500
value so that recursive function works in the sense that it receives both a greater than and lesser

4
00:00:13,500 --> 00:00:19,500
than value, regardless of where and which direction the traversal is made inside of our tree.

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

6
00:00:26,330 --> 00:00:36,230
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,230 --> 00:00:40,550
When we make this step, we don't care at this point what its greater than.

8
00:00:40,550 --> 00:00:42,680
The only condition is that it's lesser than 12.

9
00:00:42,710 --> 00:00:47,030
It can be greater than anything, but as long as it's lesser than 12, it's valid.

10
00:00:47,030 --> 00:00:52,250
So you might think, what if I just picked a small value like -10,000, for example?

11
00:00:52,550 --> 00:00:57,350
So as long as this value is greater than -10,000, then this works.

12
00:00:57,350 --> 00:01:00,950
And as we see, whenever we go left, we persist the greater than value.

13
00:01:00,950 --> 00:01:04,819
So here we're still passing the greater than -10,000.

14
00:01:05,269 --> 00:01:06,920
And so far it still works.

15
00:01:07,130 --> 00:01:11,120
But remember, we have no idea how far down this branch goes.

16
00:01:11,120 --> 00:01:16,940
And let's say down here there was a -100,000 or -1,000,000 value.

17
00:01:17,390 --> 00:01:23,210
When we do our traversal, our traversal is still going to try and say that it's within this boundary

18
00:01:23,210 --> 00:01:33,140
of -10,000 here when it tries to say if this value that we're moving to the left is greater than -10,000

19
00:01:33,290 --> 00:01:40,520
but lesser than seven here, it's going to fail because -100,000 is lesser than 10,000, but it must

20
00:01:40,520 --> 00:01:42,920
be greater than ten K, according to our rule.

21
00:01:42,920 --> 00:01:46,550
So here we see that this is indeed valid.

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

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

24
00:02:00,050 --> 00:02:03,350
infinitesimally small is negative infinity.

25
00:02:03,590 --> 00:02:10,729
So here we can actually say that when we start traversing to the left for the first time that this value

26
00:02:10,729 --> 00:02:13,910
must be greater than negative infinity, but less than 12.

27
00:02:13,910 --> 00:02:18,230
If we traverse left again, we're keeping this greater than negative infinity.

28
00:02:19,470 --> 00:02:20,970
And this is still valid.

29
00:02:20,970 --> 00:02:28,200
And no matter how far down we go, every value is going to be greater than negative infinity.

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

31
00:02:33,540 --> 00:02:36,300
we go right, we want to replace this value now.

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

33
00:02:43,290 --> 00:02:50,010
then the value of negative infinity that this next value must be greater than update it, because this

34
00:02:50,010 --> 00:02:56,160
value is obviously going to be greater than negative infinity, which means that nine being greater

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

36
00:03:01,110 --> 00:03:02,760
the condition we need to satisfy.

37
00:03:03,090 --> 00:03:09,510
So what we see is that whenever we go right, we're updating this greater than value.

38
00:03:09,660 --> 00:03:17,400
If the value that we're updating is greater than the previous value that we use to compare for greater

39
00:03:17,400 --> 00:03:23,040
than so here we're going right again, we see that the current value of nine is greater than our previous

40
00:03:23,040 --> 00:03:27,060
greater than value of seven, so we update it accordingly.

41
00:03:27,240 --> 00:03:34,830
So here we figured out a rule if we go left, keep the previous value that we are greater than if we

42
00:03:34,830 --> 00:03:35,880
go right.

43
00:03:36,090 --> 00:03:41,280
Update the value of the greater than to the current node's value.

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

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

46
00:03:51,180 --> 00:03:53,850
So update it to the current node's value.

47
00:03:53,850 --> 00:03:55,650
So this is what we've seen.

48
00:03:55,860 --> 00:03:58,320
If we go left, keep the greater than value.

49
00:03:58,320 --> 00:04:01,500
If we go right, update it to our current value.

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

51
00:04:08,220 --> 00:04:09,120
traversing.

52
00:04:09,120 --> 00:04:11,040
But what about our lesser than value?

53
00:04:11,070 --> 00:04:12,270
Let's figure this out.

54
00:04:12,300 --> 00:04:13,770
So starting from the root, let's go.

55
00:04:13,770 --> 00:04:14,460
Right.

56
00:04:14,460 --> 00:04:19,519
We know that going right are lesser than value updates to our current node value.

57
00:04:19,529 --> 00:04:25,200
This stays the exact same, but this must now be lesser than some value.

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

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

60
00:04:37,200 --> 00:04:38,760
than value to our current node.

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

62
00:04:44,310 --> 00:04:47,670
So as long as this value is lesser than infinity, this is correct.

63
00:04:48,140 --> 00:04:50,660
But what about if we were to go left instead?

64
00:04:50,960 --> 00:04:57,050
If we go left, we see now that we need to update the lesser than value to the current node's value.

65
00:04:57,050 --> 00:04:59,630
We don't keep the infinity.

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

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

68
00:05:13,040 --> 00:05:14,420
That's literally the condition.

69
00:05:14,420 --> 00:05:18,500
The node to the left of our node must be lesser than my nodes value.

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

71
00:05:22,880 --> 00:05:28,700
But we can keep the previous greater than value as long as we're going left.

72
00:05:28,700 --> 00:05:34,100
So here we figured out our relationship and what we notice is that when we start, we're going to have

73
00:05:34,100 --> 00:05:35,600
to start from the root as well.

74
00:05:35,660 --> 00:05:40,670
So what's the boundary for this condition while maintaining what we pass the the left and the right

75
00:05:40,670 --> 00:05:44,720
while it's going to be the exact same thing, but combined.

76
00:05:44,720 --> 00:05:51,590
So as long as this root value is greater than negative infinity, but lesser than infinity, it's valid,

77
00:05:51,590 --> 00:05:52,220
which is true.

78
00:05:52,220 --> 00:05:53,510
Our root value can be anything.

79
00:05:53,510 --> 00:05:54,890
So this condition makes sense.

80
00:05:54,890 --> 00:06:01,970
When you go left though, you want to replace the lesser than value as we've established with 12 instead

81
00:06:01,970 --> 00:06:02,780
of infinity.

82
00:06:03,170 --> 00:06:10,610
When you go right, you want to update the greater than value with 12 instead of negative infinity,

83
00:06:10,610 --> 00:06:14,660
and then the rules will just persist throughout the rest of this code.

84
00:06:15,050 --> 00:06:17,480
So here is my challenge to you.

85
00:06:17,510 --> 00:06:19,520
Take what we've just made.

86
00:06:19,520 --> 00:06:25,220
Really understand how we came to this conclusion by walking through this and figuring out what it is

87
00:06:25,220 --> 00:06:29,870
that we were missing at every step and try and code out this solution.

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

89
00:06:35,450 --> 00:06:41,390
of a way to use a recursive reusable bit of logic on every traversal.

90
00:06:41,390 --> 00:06:43,610
In order for this to be properly valid.

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

92
00:06:48,380 --> 00:06:49,760
up with this solution.

93
00:06:50,060 --> 00:06:52,940
So try and code it out and I'll show you how to do it in the next video.