1
00:00:01,230 --> 00:00:07,200
So in order for us to cut out our solution, I'm just going to reference this pseudocode block that

2
00:00:07,200 --> 00:00:09,420
we had written in our previous lesson.

3
00:00:10,320 --> 00:00:15,670
So here I want to initialize our function, which I'm going to call Max depth.

4
00:00:16,380 --> 00:00:21,590
We also know that this is going to be a recursive function, so I'm going to pass it.

5
00:00:21,600 --> 00:00:23,220
The two arguments we've had to find.

6
00:00:23,790 --> 00:00:25,410
The first is going to be the node.

7
00:00:25,420 --> 00:00:30,450
The next is going to be the current depth that we have calculated thus far.

8
00:00:31,830 --> 00:00:39,480
We also want to do a check here and say that if there is no value for node, so if notis falsey, which

9
00:00:39,480 --> 00:00:45,680
we know that null is falsey, then we just want to return the current depth.

10
00:00:50,090 --> 00:00:57,080
Alternatively, if Noad does have a value, then I want to increment the value of this current depth

11
00:00:57,080 --> 00:00:57,860
by one.

12
00:01:00,830 --> 00:01:08,340
And then the next thing that we're going to do is just return the maximum value of calling our recursion.

13
00:01:08,810 --> 00:01:13,550
So I'm going to say return math, Max, as our second base case.

14
00:01:14,330 --> 00:01:24,140
And here I want to call Max depth on no dot left while passing in current depth.

15
00:01:26,920 --> 00:01:32,500
And similarly, I am going to do the same thing on the right side, I'm just going to do it down here

16
00:01:32,500 --> 00:01:33,910
because we don't have enough room.

17
00:01:34,750 --> 00:01:38,730
So I'm going to call Max Depth on node, right.

18
00:01:40,570 --> 00:01:42,990
Also passing in current depth.

19
00:01:43,720 --> 00:01:47,260
So this is actually almost the exact same as our pseudocode.

20
00:01:48,700 --> 00:01:50,260
But that's our solution.

21
00:01:50,470 --> 00:01:51,320
Very simple.

22
00:01:52,090 --> 00:01:55,540
It's pretty much just exactly what we explored in our pseudocode.

23
00:01:55,900 --> 00:02:01,240
Now, this might not always be the case when you do these binary tree questions that your pseudocode

24
00:02:01,240 --> 00:02:03,840
matches the actual final solution so closely.

25
00:02:04,360 --> 00:02:10,200
The main idea of the pseudocode is to capture the bulk of the logic around how we solve this question.

26
00:02:10,210 --> 00:02:13,690
But luckily for us with this question, it's pretty much the exact same thing.

27
00:02:14,560 --> 00:02:20,560
As always, there is a link to the actual solution if you cannot read the handwriting that I've got

28
00:02:20,560 --> 00:02:22,590
here inside of your resources folder.

29
00:02:23,320 --> 00:02:26,080
But let's analyze the space and time complexity here.

30
00:02:27,200 --> 00:02:34,700
So when we think about time, complexity in a worst case scenario, we can imagine that this binary

31
00:02:34,700 --> 00:02:35,900
tree is flipped.

32
00:02:36,540 --> 00:02:40,810
And yes, while we look at this recursion, we explore the left first.

33
00:02:41,840 --> 00:02:46,850
If this tree was flipped such that this longest path was on the right side instead of on the left side,

34
00:02:47,240 --> 00:02:50,750
then it would be the very last note that we would explore.

35
00:02:50,990 --> 00:02:56,210
What that means is essentially we end up exploring every single node inside of this tree.

36
00:02:56,840 --> 00:03:05,180
So what this means is that our time complexity has a worst case of oh, of and being the total number

37
00:03:05,180 --> 00:03:06,320
of nodes in the tree.

38
00:03:07,490 --> 00:03:08,930
What about space?

39
00:03:08,930 --> 00:03:10,520
Complexity, space?

40
00:03:10,520 --> 00:03:13,820
Complexity is going to be the size of our recursion.

41
00:03:15,440 --> 00:03:24,320
Now, in the example with this binary tree or recursive call can get as large as five because we are

42
00:03:24,320 --> 00:03:29,720
going to traverse five nodes down, which means that we are going to recursively call five different

43
00:03:29,720 --> 00:03:32,020
function calls to get to this last note.

44
00:03:32,750 --> 00:03:39,550
So you can see this as the case where the height of the tree is the size of the recursion.

45
00:03:39,890 --> 00:03:48,260
And in a perfectly balanced tree, the height of the tree is of log ln and being the number of notes.

46
00:03:48,980 --> 00:03:55,670
If you don't remember why this is the case, we are dividing the number of nodes by two in order to

47
00:03:55,670 --> 00:03:57,790
fit equal size in the levels.

48
00:03:57,800 --> 00:04:06,170
So in a perfectly balanced, fully complete tree, every single level is filled and in that case, log

49
00:04:06,170 --> 00:04:08,080
in is the height of the tree.

50
00:04:08,090 --> 00:04:09,370
But this is the best case.

51
00:04:09,920 --> 00:04:11,270
What about the worst case?

52
00:04:11,870 --> 00:04:18,410
The worst case is where we consider that tree that I originally showed you, the tree where every single

53
00:04:18,410 --> 00:04:23,370
node sits on the right child of the actual value.

54
00:04:24,080 --> 00:04:29,840
So here when you have a binary tree of this size, what is the height of the tree?

55
00:04:30,440 --> 00:04:31,670
The height of the tree is.

56
00:04:32,390 --> 00:04:39,440
So that's why you have to consider as far as space complexity goes, if we're recursively calling down

57
00:04:39,440 --> 00:04:46,850
every single child of every single node, then our recursive stack is the size of this tree, which

58
00:04:46,850 --> 00:04:47,600
is N.

59
00:04:48,020 --> 00:04:55,270
So the worst case scenario is we receive a skewed tree like this and we have O of NP as the space complexity.

60
00:04:56,000 --> 00:05:00,080
So space you want to consider worst case scenario of end.

61
00:05:01,130 --> 00:05:02,730
And this is our solution.

62
00:05:03,500 --> 00:05:06,100
This is generally the best solution you can get.

63
00:05:06,320 --> 00:05:11,000
And the reason why we are able to get to this best case solution right away is because of the way that

64
00:05:11,000 --> 00:05:13,640
we concern ourselves with how to solve this question.

65
00:05:14,330 --> 00:05:22,190
Generally speaking, you can with binary tree questions half the time, get straight to the proper solution

66
00:05:22,370 --> 00:05:28,580
when you consider all of the cases of what you need to apply here, which is search type and traversal

67
00:05:28,580 --> 00:05:36,530
type here at this point with a lot of our recursive solutions in order to practice, we want to go straight

68
00:05:36,530 --> 00:05:39,110
for maybe the optimal solution.

69
00:05:39,110 --> 00:05:44,720
If it's obvious to us that the steps we take to get there will help us get to the solution.

70
00:05:45,140 --> 00:05:50,440
So you'll notice with some of these questions that we do, we're not going to come up with a brute force

71
00:05:50,450 --> 00:05:55,730
solution first, because sometimes the brute force solution doesn't actually get us to the optimal solution.

72
00:05:56,270 --> 00:06:02,180
So it's really going to be something that comes to you with more practice of these questions, which

73
00:06:02,180 --> 00:06:03,080
we are going to do.

74
00:06:03,770 --> 00:06:09,380
So now that we have a general basic idea of how to tackle some binary tree questions, let's keep practicing

75
00:06:09,380 --> 00:06:10,400
with another question.