1
00:00:00,390 --> 00:00:01,380
Welcome back, everyone.

2
00:00:02,160 --> 00:00:06,210
Up until this point, we've only looked at normal binary trees.

3
00:00:06,720 --> 00:00:13,710
Sometimes interviewers will like to throw in the complexity by mentioning that the tree is full and

4
00:00:13,710 --> 00:00:14,730
or complete.

5
00:00:15,600 --> 00:00:20,400
In this lesson, we're going to look at a question where the binary tree will be one of these types.

6
00:00:20,400 --> 00:00:26,700
And we're going to analyze how that changes the insights that we can glean from this type of binary

7
00:00:26,700 --> 00:00:27,090
tree.

8
00:00:28,110 --> 00:00:33,420
So first, let's just quickly go over the differences between full and complete trees, a full tree

9
00:00:33,420 --> 00:00:38,500
is one where every tree node has either zero children or two children.

10
00:00:38,670 --> 00:00:40,500
That's the only stipulation.

11
00:00:40,710 --> 00:00:44,780
This tree can be any level and not all levels can be completely full.

12
00:00:45,120 --> 00:00:51,870
All that matters is that any tree node inside of this tree has either two children or no children.

13
00:00:52,110 --> 00:00:57,440
A complete tree, on the other hand, is one where every level is completely full.

14
00:00:58,290 --> 00:01:01,710
The only level that doesn't need to be fall is the last level.

15
00:01:01,740 --> 00:01:08,220
And even if it's not, all of the nodes must be pushed as far left as possible, meaning that you could

16
00:01:08,220 --> 00:01:13,830
end up with a tree, which in this case with this given structure, has three nodes at the bottom.

17
00:01:14,070 --> 00:01:18,000
All push the left though, or two nodes or one node.

18
00:01:18,630 --> 00:01:25,020
The trick is just that that last level, the nodes that are there must be as left as they can be.

19
00:01:25,530 --> 00:01:28,290
A tree can also be full and complete.

20
00:01:28,620 --> 00:01:35,550
In this case, every level is filled with nodes and here you can see it fulfills both the stipulations.

21
00:01:35,980 --> 00:01:43,290
It is a full tree because every node has either two children or no children, and it is complete because

22
00:01:43,290 --> 00:01:47,340
every level is completely filled, including the last level.

23
00:01:48,190 --> 00:01:53,740
Generally speaking, there's more complexity and nuance to receiving a complete treat rather than a

24
00:01:53,740 --> 00:01:57,610
full tree, and we're going to see why in this next question.

25
00:01:58,550 --> 00:02:04,940
The question says that given a complete binary tree count, the number of nodes in the tree, we can

26
00:02:04,940 --> 00:02:11,150
see that if we were given this binary tree structure, if we count the number of nodes here, we'll

27
00:02:11,150 --> 00:02:12,770
end up with 15 nodes.

28
00:02:13,400 --> 00:02:19,690
But because a complete binary tree doesn't necessarily have to have that bottom level completely full,

29
00:02:20,060 --> 00:02:25,970
we could receive this binary tree, which has 12 nodes or this binary tree which has eight nodes.

30
00:02:26,360 --> 00:02:32,780
When we begin to solve for this actual question, we have to make sure to consider this as the main

31
00:02:32,780 --> 00:02:37,680
case and the main difference about different types of complete trees we could receive.

32
00:02:38,480 --> 00:02:43,100
So from here, let's move on to actually verifying any constraints about the problem.

33
00:02:44,050 --> 00:02:48,040
The question, again, is pretty straightforward, there's not that many constraints that we need.

34
00:02:48,220 --> 00:02:54,550
We know that if we get a empty binary tree, we can just return zero since we're just counting nodes

35
00:02:54,550 --> 00:02:54,800
here.

36
00:02:55,270 --> 00:02:58,030
So let's actually write out some of our test cases.

37
00:02:59,300 --> 00:03:05,870
To save us some time, I've imported in the three complete binary trees that we have just seen here,

38
00:03:05,870 --> 00:03:10,820
when you come up with the actual test cases yourself, you want to think about the fact that it's a

39
00:03:10,820 --> 00:03:11,980
complete treat.

40
00:03:12,590 --> 00:03:18,500
This means that every level is completely full, except for the last level where if there are nodes,

41
00:03:18,500 --> 00:03:24,710
they must be pushed as far left as possible right away to conditional cases should jump out at you.

42
00:03:25,040 --> 00:03:28,970
The first one should be where the level is completely full.

43
00:03:29,450 --> 00:03:32,670
The other is where the level only has one value.

44
00:03:33,320 --> 00:03:38,210
The third case here can be any one in between where it's not completely full.

45
00:03:38,210 --> 00:03:41,580
But it's also not just one value in this case.

46
00:03:41,780 --> 00:03:48,470
This tree represents the case where it's any number of values filled as long as they're completely to

47
00:03:48,470 --> 00:03:49,030
the left.

48
00:03:49,730 --> 00:03:54,860
These three conditions may not necessarily contribute one hundred percent to all of the insights that

49
00:03:54,860 --> 00:03:58,100
you'll need, but at the very least, it's a good place to start.

50
00:03:58,100 --> 00:04:03,140
As far as what might jump out at you and what your intuition might tell you that you want to consider.

51
00:04:03,860 --> 00:04:10,190
So at this point, you might also be thinking this solution seems a little bit way too obvious.

52
00:04:10,700 --> 00:04:13,430
When we think about whether or not the traversal matters.

53
00:04:13,460 --> 00:04:17,900
We know that we want to navigate through the tree to count the nodes, but we don't really care about

54
00:04:17,900 --> 00:04:21,320
the values inside since we're just counting notes here.

55
00:04:21,470 --> 00:04:29,870
We also know that our breadth of research and depth research traverses both take a time of of ln the

56
00:04:29,870 --> 00:04:32,210
spaces also generally of NP.

57
00:04:32,510 --> 00:04:38,480
And if that's the case, both before a search and deafer search work, because they each touch every

58
00:04:38,480 --> 00:04:40,160
node a single time.

59
00:04:40,770 --> 00:04:45,440
And what we're doing is essentially just accumulating the count for every node that gets touched.

60
00:04:45,440 --> 00:04:50,810
So breadth of research or depth research are both valid and they seem like there's very minimal code

61
00:04:50,810 --> 00:04:55,280
changes to implement in order to implement that solution here.

62
00:04:55,290 --> 00:04:57,530
You want to voiced this concern to your interviewer.

63
00:04:57,920 --> 00:05:02,750
You just want to say that it seems really obvious that I can leverage breadth of research or depth research

64
00:05:02,750 --> 00:05:04,520
and just count the nodes along the way.

65
00:05:04,670 --> 00:05:06,950
But there must be a more optimal solution.

66
00:05:07,190 --> 00:05:09,430
And your interview will probably respond back.

67
00:05:09,440 --> 00:05:10,370
Yes, you're correct.

68
00:05:10,370 --> 00:05:13,820
There is a more optimal solution here and from here.

69
00:05:13,820 --> 00:05:14,840
You want to say that?

70
00:05:15,020 --> 00:05:21,950
Let me focus in on the fact that it is a complete binary tree because the complete binary tree is the

71
00:05:21,950 --> 00:05:23,710
real trick to this question.

72
00:05:23,900 --> 00:05:29,540
The fact that we received a complete binary tree and the fact that the question seems so obvious to

73
00:05:29,540 --> 00:05:34,970
implement means that the complete binary tree itself is the challenge.

74
00:05:35,450 --> 00:05:42,140
We need to figure out what kind of insights we can derive from a complete binary tree to bring the time

75
00:05:42,320 --> 00:05:44,390
or the space down from zero of.

76
00:05:45,290 --> 00:05:48,800
So when we think about that, we let those two things guide our thoughts.

77
00:05:49,070 --> 00:05:54,200
What is lower than oh, then there's only of log ln and low of one.

78
00:05:54,710 --> 00:06:01,340
If this is the case then that means that in order to solve for this problem, we want to achieve something

79
00:06:01,340 --> 00:06:04,310
within this realm of Lagann or one.

80
00:06:04,880 --> 00:06:08,900
So let's look at the structure and think back even before binary trees.

81
00:06:09,170 --> 00:06:15,560
What are the things that we know that can achieve log n that are somewhat tangentially related to the

82
00:06:15,560 --> 00:06:16,250
structure?

83
00:06:17,280 --> 00:06:23,190
Well, this shape kind of looks like our divide and conquer pattern when we think back on Quicksort

84
00:06:23,190 --> 00:06:29,040
of Mursau and the pattern that we had, we originated with the full array and we would divide it in

85
00:06:29,040 --> 00:06:34,890
half and divide those in half and keep going until we had singular values which are easy to sort.

86
00:06:35,520 --> 00:06:42,420
What we knew was that that shape looks pretty much like a complete binary tree that's also full.

87
00:06:43,390 --> 00:06:45,790
So here, what are the insights we know about that?

88
00:06:46,240 --> 00:06:48,790
Well, let's look at the height of the tree.

89
00:06:49,300 --> 00:06:55,810
When we think about the height of a tree that is completely full, the number of nodes there are, we

90
00:06:55,810 --> 00:06:57,280
can represent as an.

91
00:06:58,550 --> 00:07:05,210
What we also know is that this is essentially a log base, two of N, which in our case here and being

92
00:07:05,210 --> 00:07:08,990
15 yield's us three point nine something which is pretty much just for.

93
00:07:10,040 --> 00:07:15,260
What we also notice is that four is the number of levels that exist in this tree.

94
00:07:15,920 --> 00:07:18,800
So here there is some relation to log.

95
00:07:18,800 --> 00:07:27,210
And what we also know is that the values inside of the very bottom of this tree are an over two.

96
00:07:27,230 --> 00:07:30,070
I've taught you this before about complete trees.

97
00:07:30,080 --> 00:07:36,560
When we analyzed looking at breath research and the size of our Q holding all the values in a full bottom

98
00:07:36,560 --> 00:07:42,280
level of a complete tree here, this is an over two and maybe this is also significant in some way.

99
00:07:42,950 --> 00:07:48,980
So I want you to think about all of these things and just try and figure out, at least with your intuition,

100
00:07:49,130 --> 00:07:53,600
what kind of insights might be impactful regarding these complete trees.

101
00:07:54,320 --> 00:07:57,980
In the next lesson, I'm going to show you how to actually solve this problem.

102
00:07:57,980 --> 00:08:00,960
But I do want you to try and see if you can figure it out.

103
00:08:01,010 --> 00:08:07,220
There are a lot of tricks here, but it mostly revolves around thinking about the shape here and thinking

104
00:08:07,220 --> 00:08:10,710
about what different things we have that can achieve log of.

105
00:08:10,740 --> 00:08:13,940
And it's not just the height of this tree that's log in.

106
00:08:14,240 --> 00:08:16,360
There's also something else that we have leverage before.

107
00:08:16,370 --> 00:08:19,130
And the last thing I'm going to give you about that is binary search.

108
00:08:19,580 --> 00:08:25,790
Can we combine all of these concepts together in some way regarding these binary tree questions to come

109
00:08:25,790 --> 00:08:26,820
up with an optimal solution?

110
00:08:27,140 --> 00:08:30,590
I'm going to leave that to you to try and I'll show you how to do it in the next video.