1
00:00:00,470 --> 00:00:01,650
Welcome back, everyone.

2
00:00:02,090 --> 00:00:09,440
So I know we just learned a bunch of little topics inside of binary trees that seem a little bit daunting,

3
00:00:09,560 --> 00:00:13,430
especially around how they get incorporated in our technical interviews.

4
00:00:13,910 --> 00:00:18,350
Now, binary trees is definitely one of the more complex data structures.

5
00:00:18,350 --> 00:00:25,580
And there are a lot of variations of questions that show up in binary trees because there are so many

6
00:00:25,580 --> 00:00:30,290
little topics that can be added for that complexity with our questions.

7
00:00:30,420 --> 00:00:35,870
But in this section, I'm going to show you a very solid approach that you can apply to solving these

8
00:00:35,870 --> 00:00:37,100
binary tree questions.

9
00:00:37,250 --> 00:00:42,980
We're going to tackle all the topics that can get incorporated into a binary tree that we just learned

10
00:00:42,980 --> 00:00:49,100
in our appendix from full versus complete trees, the different kinds of traversal, breath versus depth,

11
00:00:49,100 --> 00:00:52,520
first search and binary trees versus binary search trees.

12
00:00:52,790 --> 00:00:59,750
But the best place to begin is to focus on just binary trees and not add the complexity of binary search

13
00:00:59,750 --> 00:01:00,270
trees yet.

14
00:01:01,160 --> 00:01:05,660
So with binary trees, there are two reversals and there are search types.

15
00:01:05,660 --> 00:01:10,940
We already know there's breadth, first search and depth, first search, as well as preorder in order

16
00:01:10,940 --> 00:01:12,710
and post order traversal.

17
00:01:13,400 --> 00:01:19,310
These five main topics all revolve around navigating through a binary tree.

18
00:01:19,850 --> 00:01:28,640
The key with this is trying to figure out which of these five tools you can bring into your solution

19
00:01:28,910 --> 00:01:35,090
so it can help you actually execute the logical solution you come up with for your question.

20
00:01:35,450 --> 00:01:38,930
And we're going to explore all this, if that seems a little confusing.

21
00:01:38,930 --> 00:01:40,250
But I want you to keep that in mind.

22
00:01:40,610 --> 00:01:47,930
These are the tools that will best help you implement your solution when it comes to navigating through

23
00:01:47,960 --> 00:01:49,270
your binary tree.

24
00:01:49,640 --> 00:01:56,210
And we're going to start with a very easy binary tree question just to get familiar with this exact

25
00:01:56,240 --> 00:01:57,100
navigation.

26
00:01:57,740 --> 00:02:04,730
So the question is going to say, given a binary tree, find its maximum depth here.

27
00:02:04,730 --> 00:02:12,740
A maximum depth is defined as the number of nodes along the longest path from the root node to the furthest

28
00:02:12,740 --> 00:02:13,580
leaf node.

29
00:02:14,420 --> 00:02:21,020
So when we look at this, let's say we were given this binary tree structure, we want to find the maximum

30
00:02:21,020 --> 00:02:25,880
path, which is defined as the distance from that root node, which is the green node at the top to

31
00:02:25,880 --> 00:02:29,300
the furthest leaf node, which is that orange node at the bottom.

32
00:02:30,170 --> 00:02:34,730
Here we can see the longest path would be highlighted by these green nodes.

33
00:02:34,910 --> 00:02:38,780
And if we count the number of nodes we see that we end up with five.

34
00:02:39,080 --> 00:02:45,590
So the answer here that we would return if given this binary tree structure is five, because the five

35
00:02:45,590 --> 00:02:50,990
nodes highlighted in green is the maximum depth or the longest path.

36
00:02:51,930 --> 00:02:58,560
So with this in mind, let's solve our question, and the first step, as we always do, is we need

37
00:02:58,560 --> 00:02:59,900
to verify the constraints.

38
00:03:00,360 --> 00:03:02,760
So this question is pretty straightforward.

39
00:03:02,770 --> 00:03:07,780
So there really aren't that many constraints for us to ask about one.

40
00:03:07,830 --> 00:03:11,220
What we can ask for our own measure is what do we return?

41
00:03:11,220 --> 00:03:16,740
If the tree is empty, if the tree is empty, we just return zero because maximum depth here will be

42
00:03:16,740 --> 00:03:17,160
zero.

43
00:03:17,550 --> 00:03:23,100
Similarily, if we receive a tree where there's just one node, which is the root node, we can return

44
00:03:23,100 --> 00:03:25,800
one because that is still the depth of one.

45
00:03:26,700 --> 00:03:32,820
This question is not as complex because we are just returning the maximum depth, which is a number,

46
00:03:32,910 --> 00:03:38,880
we're not returning the path itself, which means that if there are multiple branches that time for

47
00:03:38,880 --> 00:03:44,820
the same maximum depth, we don't have to return either of those as our consideration.

48
00:03:44,970 --> 00:03:51,210
All we have to return is the maximum depth number, which is what makes this question really easy and

49
00:03:51,210 --> 00:03:51,960
straightforward.

50
00:03:52,530 --> 00:03:56,910
So from here on, we can move on to the next step, which is to write out some test cases.

51
00:03:58,080 --> 00:04:03,750
When coming up with test cases for binary tree questions, you want the best case, you want the null

52
00:04:03,750 --> 00:04:08,250
cases, but there's actually one additional case you want to consider, which is considered a worst

53
00:04:08,250 --> 00:04:08,600
case.

54
00:04:08,610 --> 00:04:09,970
And I'll show you what that looks like.

55
00:04:10,620 --> 00:04:17,040
So here with our best case, we're just going to duplicate that tree we saw when we first explored this

56
00:04:17,040 --> 00:04:17,560
question.

57
00:04:18,240 --> 00:04:24,850
So with this example, this tree is going to have no values inside of the tree nuts.

58
00:04:25,260 --> 00:04:34,530
The reason for this is because we don't care about any values inside of our binary tree, as we already

59
00:04:34,530 --> 00:04:35,020
saw.

60
00:04:35,220 --> 00:04:39,920
We're simply looking for the depth of this tree or the maximum depth of the tree.

61
00:04:40,080 --> 00:04:42,720
The values for us do nothing.

62
00:04:43,530 --> 00:04:50,160
And with this one, we count the nodes from this route all the way down to the furthest lymph node,

63
00:04:50,160 --> 00:04:52,570
and we see that this gives us five.

64
00:04:52,770 --> 00:04:57,440
So the answer for this tree is going to be five for our null cases.

65
00:04:57,450 --> 00:05:02,970
We know there's a chance where we get null, meaning that there are no nodes as the binary tree.

66
00:05:03,300 --> 00:05:09,840
In this case, we're going to return zero similarily if we receive just a single node, which is going

67
00:05:09,840 --> 00:05:12,420
to be just the root node with no children.

68
00:05:12,750 --> 00:05:14,040
We want to return one.

69
00:05:15,060 --> 00:05:21,990
So this is the three cases we have our best case, we have our null cases or our single case, but we

70
00:05:21,990 --> 00:05:24,210
also have that worst case now.

71
00:05:24,210 --> 00:05:31,500
The worst case scenario for any binary tree that we generally should consider is one where we have all

72
00:05:31,500 --> 00:05:35,200
of the nodes that sit along one path.

73
00:05:35,850 --> 00:05:41,610
So here I'm just going to write this in and fill out that left side as null.

74
00:05:43,210 --> 00:05:49,450
But what you'll notice is that in order to traverse down any of these nodes, you're going to follow

75
00:05:49,450 --> 00:05:50,320
along the path.

76
00:05:51,280 --> 00:05:57,130
This is significant because when it comes to your space and time complexity, it's always going to be

77
00:05:57,130 --> 00:06:02,950
out of end because worst case, if you need to reach this node, you're going to have to go through

78
00:06:02,950 --> 00:06:04,550
the entire tree.

79
00:06:04,930 --> 00:06:08,440
And this is going to impact both space and time complexity.

80
00:06:08,440 --> 00:06:12,370
And I'll show you when we actually explore solutions for this question.

81
00:06:12,880 --> 00:06:19,180
But in this case, we know that this answer is going to be five because the first node is five notes

82
00:06:19,180 --> 00:06:19,560
down.

83
00:06:20,380 --> 00:06:25,730
But this, again, is mainly just an impact on space and time, complexity considerations.

84
00:06:26,410 --> 00:06:31,290
So now that we have our test cases, I want you to try and come up with a solution yourself.

85
00:06:31,870 --> 00:06:38,470
So take our best case test case and consider our worst cases as well and see if you can think of a logical

86
00:06:38,470 --> 00:06:39,010
solution.

87
00:06:40,040 --> 00:06:44,870
It might be difficult because you don't really know how to apply some of these ideas yet, but it's

88
00:06:44,870 --> 00:06:49,910
still good to see if you can fight with the problem a little bit and come up with anything yourself.

89
00:06:50,360 --> 00:06:52,790
If not, I'm going to show you in the next lesson.

90
00:06:53,060 --> 00:06:54,260
So I'll see you in that lesson.