1 00:00:00,270 --> 00:00:01,270 Welcome back, everyone. 2 00:00:01,770 --> 00:00:08,970 Hopefully you got a chance to really think about this complete binary tree question, here is an example 3 00:00:08,970 --> 00:00:14,760 where when I mentioned before, does the traversal matter and does it drive you towards breath for a 4 00:00:14,780 --> 00:00:16,050 search and deeper search? 5 00:00:16,230 --> 00:00:18,510 I said that ninety five percent of the time it does. 6 00:00:18,510 --> 00:00:19,840 Five percent of the time it doesn't. 7 00:00:20,280 --> 00:00:26,460 This question is a perfect example of one where it doesn't because it leverages more on our critical 8 00:00:26,460 --> 00:00:32,910 and abstract thinking involving the complete binary tree structure than the actual traversal algorithms 9 00:00:32,910 --> 00:00:36,290 that we've been practicing for the last few binary tree questions. 10 00:00:36,870 --> 00:00:42,180 So to begin with, what we need to really think about is the fact that this is a complete tree and we 11 00:00:42,180 --> 00:00:46,230 have to think about what characteristics are there as well as what goal we're trying to achieve. 12 00:00:46,590 --> 00:00:50,080 In our particular case, we're trying to count the number of nodes in this tree. 13 00:00:50,400 --> 00:00:55,830 So let's take the idea that we're looking for the total number of nodes in any given tree, but also 14 00:00:55,830 --> 00:00:57,220 the fact that it's a complete tree. 15 00:00:57,600 --> 00:00:59,160 What are the facts about complete trees? 16 00:00:59,550 --> 00:01:03,360 Complete trees are full at every single level except for the last one. 17 00:01:03,570 --> 00:01:10,260 So in a way, you can see that you almost have to break up this problem of counting the nodes in the 18 00:01:10,260 --> 00:01:12,120 tree into two sections. 19 00:01:12,540 --> 00:01:17,750 The first section is every level except for the very last level. 20 00:01:18,330 --> 00:01:20,850 The second section is the very last level. 21 00:01:21,030 --> 00:01:25,350 As we see in all of these three different binary trees we've drawn. 22 00:01:25,680 --> 00:01:31,680 They are of the exact same height, but the only variability in the number of nodes lives in the last 23 00:01:31,680 --> 00:01:32,070 level. 24 00:01:32,370 --> 00:01:39,120 So if we break this problem into two sections, well, we're able to do is say how efficiently can I 25 00:01:39,120 --> 00:01:45,870 count the number of nodes above this last level and then how efficiently can I count the number of nodes 26 00:01:46,140 --> 00:01:47,240 in this last level. 27 00:01:47,400 --> 00:01:53,150 So let's start with this first portion, which is every level of the nodes except for the last level. 28 00:01:53,670 --> 00:01:57,990 We also want to keep in mind that for each of these sections, we're trying to achieve an optimal time 29 00:01:57,990 --> 00:02:04,890 better than zero of NP because o of and is what we can achieve already with deeper search and breathless 30 00:02:04,890 --> 00:02:05,340 search. 31 00:02:05,370 --> 00:02:11,190 A more convoluted solution that still achieves O of end is not a more optimal solution, which means 32 00:02:11,190 --> 00:02:19,350 that each of these sections must be able to be performed in either O of log N or O of one, because 33 00:02:19,350 --> 00:02:23,290 these are the only two complexities that are more performant than O of end. 34 00:02:23,850 --> 00:02:30,090 So knowing that, let's think about how can we calculate the size of this part of the tree. 35 00:02:31,020 --> 00:02:36,840 If we look at this tree, we know that every single node at these levels that we're considering right 36 00:02:36,840 --> 00:02:38,280 now must be completely full. 37 00:02:38,550 --> 00:02:42,390 So what's the relationship and what's the best way we can get these values? 38 00:02:42,900 --> 00:02:46,530 If we think about it, these values are always doubling. 39 00:02:46,530 --> 00:02:51,600 And what we think about doubling and then doubling and then doubling, what we're saying is that we're 40 00:02:51,720 --> 00:02:56,580 essentially achieving two to the exponent of some value in this case. 41 00:02:56,580 --> 00:03:02,790 Let's use this intuition and figure out what the values are for this so that we can calculate the number 42 00:03:02,790 --> 00:03:03,900 of notes here. 43 00:03:03,900 --> 00:03:11,670 We have one node two to what gives us one two to the zero gives us one similarily, two to what gives 44 00:03:11,670 --> 00:03:12,180 us two. 45 00:03:12,570 --> 00:03:14,310 Well, two to one gives us two. 46 00:03:14,940 --> 00:03:19,470 And then the next level is four two to the power to gives us for the next level. 47 00:03:19,470 --> 00:03:23,250 We have eight two to the three gives us eight here. 48 00:03:23,250 --> 00:03:26,940 I'm just showing you that this is two to the three will give us the eight value. 49 00:03:26,940 --> 00:03:32,310 But once again we don't know if this level is completely full with a complete tree, but you can see 50 00:03:32,310 --> 00:03:34,440 the relationship very clearly here. 51 00:03:34,440 --> 00:03:38,520 If we were to count the number of nodes, we see that there's one, two, three, four, five, six, 52 00:03:38,520 --> 00:03:40,890 seven nodes in this top half. 53 00:03:41,780 --> 00:03:46,220 What we can also do is just add these values together, two to the zero, which is one, two to the 54 00:03:46,220 --> 00:03:48,730 one, which is two, two to the two, which is four. 55 00:03:48,740 --> 00:03:52,120 So one plus two plus four also gives us seven. 56 00:03:53,000 --> 00:03:58,180 If we look at this relationship, though, we noticed that at this very last level, which is two to 57 00:03:58,180 --> 00:03:59,960 the three, this gives us eight. 58 00:04:00,620 --> 00:04:04,370 If we were to write out all of these values, we'd say that there's one here. 59 00:04:04,880 --> 00:04:07,610 Let me just erase these so we're more clear here. 60 00:04:08,580 --> 00:04:14,370 We have one at the first level, then two at the next level, then for the next level, then eight at 61 00:04:14,370 --> 00:04:18,990 the next level, then we have 16 at the falling level because it's two to the four. 62 00:04:19,260 --> 00:04:23,730 And similarly, the next level of two to the five, we double 16, which gives us thirty to. 63 00:04:24,540 --> 00:04:31,950 Let's think about the relationship between this portion of the tree and this next level of values here. 64 00:04:32,610 --> 00:04:40,770 We can see very clearly that if we had a tree of this size just up until this point. 65 00:04:42,160 --> 00:04:46,240 The number of values in this portion of the tree is equal to three. 66 00:04:47,750 --> 00:04:54,380 At the next level, it's equal to four, four minus one also gives us three similarily eight minus one 67 00:04:54,380 --> 00:05:01,220 gives us seven, which is the same as the number of values that we are looking for right here in this 68 00:05:01,220 --> 00:05:01,890 part of the tree. 69 00:05:02,780 --> 00:05:08,870 We can imagine then that if we were to count the number of values in the whole tree, which is full, 70 00:05:08,870 --> 00:05:14,690 it's one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13, 14, 15, 15 71 00:05:14,690 --> 00:05:16,650 is one less than the next level. 72 00:05:17,060 --> 00:05:25,910 So what we can say is that the value of the number of nodes in this upper portion of the tree is equal 73 00:05:25,910 --> 00:05:33,380 to two to the height of the tree, minus one and then minus one from that total value. 74 00:05:33,860 --> 00:05:40,340 The reason why it's H minus one is because the height value is equal to for this tree is of height four. 75 00:05:40,790 --> 00:05:45,310 But we are assuming that the base height is at two to the zero. 76 00:05:45,710 --> 00:05:50,240 So we want to subtract one to get the number of nodes at this level, which is eight. 77 00:05:50,390 --> 00:05:55,580 And then we want to subtract one from eight to get the total number of nodes here. 78 00:05:56,390 --> 00:05:59,720 So that's why we got two to the minus one, minus one. 79 00:06:00,530 --> 00:06:04,970 This mathematical calculation runs in O of one time, which is great. 80 00:06:05,330 --> 00:06:07,460 But what about getting the actual height value? 81 00:06:08,240 --> 00:06:13,360 What's the time it takes to get the height of the tree and what's the best way that we can do that? 82 00:06:13,970 --> 00:06:18,950 Well, when we look at these three variations of our complete binary tree, we see that this tree is 83 00:06:18,950 --> 00:06:24,490 the one that's the most limiting because it only has one value inside of its last level. 84 00:06:24,950 --> 00:06:30,320 So if we were to use this as our worst case scenario to determine the height, the way that we would 85 00:06:30,320 --> 00:06:36,410 do it is we would start from the very root node, which is the node that we receive in our function, 86 00:06:36,830 --> 00:06:42,680 and we would traverse down depth first search all the way to the very bottom until we find a node where 87 00:06:42,680 --> 00:06:45,470 the left next value is equal to null. 88 00:06:46,070 --> 00:06:50,490 If we counted the number of steps that we took along the way, then we could easily get the height. 89 00:06:50,810 --> 00:06:53,600 So if we initialize at zero, we get to the root node. 90 00:06:53,600 --> 00:06:54,380 So we get one. 91 00:06:54,530 --> 00:06:55,250 Then we go left. 92 00:06:55,250 --> 00:06:57,380 It's two, then we go left, it's three. 93 00:06:57,380 --> 00:06:57,980 Then we go left. 94 00:06:57,980 --> 00:06:58,520 It's four. 95 00:06:58,700 --> 00:07:01,190 And once we try and go left again, we see that the value is null. 96 00:07:01,370 --> 00:07:06,920 So four is the actual height of our tree and now we've managed to get our value for H. 97 00:07:07,310 --> 00:07:11,800 But what's the performance of doing this traversal here? 98 00:07:11,810 --> 00:07:16,070 What we see is that we took four steps, which is the height of the tree. 99 00:07:16,430 --> 00:07:20,220 So we can say that in any case, it runs end of time. 100 00:07:20,630 --> 00:07:23,000 Now, what is the height of a complete binary tree? 101 00:07:23,240 --> 00:07:24,110 We already know this. 102 00:07:24,500 --> 00:07:27,470 This is log of N log base. 103 00:07:27,470 --> 00:07:34,160 Two of the full number of nodes in this tree is equal to the height of the tree so long and gives us 104 00:07:34,160 --> 00:07:35,300 the actual height. 105 00:07:36,110 --> 00:07:41,450 So this means that this runtime for finding the height is O of log N. 106 00:07:42,260 --> 00:07:48,770 If we combine it with the mathematical calculation then it's O of log N plus O of one of one is significantly 107 00:07:48,770 --> 00:07:49,220 smaller. 108 00:07:49,220 --> 00:07:55,640 So we drop it and log and becomes the time it takes for us to calculate the number of nodes in this 109 00:07:55,640 --> 00:07:58,390 portion of any complete binary tree. 110 00:07:58,940 --> 00:08:02,180 This portion is not limited to the binary tree of this size. 111 00:08:02,270 --> 00:08:03,880 It's any complete binary tree. 112 00:08:03,900 --> 00:08:06,080 This calculation is consistent. 113 00:08:06,590 --> 00:08:11,300 So now that we understand how to get the number of nodes up here, we have to tackle getting the number 114 00:08:11,300 --> 00:08:12,650 of nodes down here. 115 00:08:13,460 --> 00:08:19,940 So I actually want you to try and figure out a way to get the number of nodes down at this last level 116 00:08:20,720 --> 00:08:21,050 here. 117 00:08:21,050 --> 00:08:22,730 I will give you a couple of hints. 118 00:08:23,240 --> 00:08:30,140 You want to think about what it is that you want to find while keeping in mind the condition that for 119 00:08:30,320 --> 00:08:36,170 all the nodes that could be in this level, they must all be pushed to the very left, meaning that 120 00:08:36,170 --> 00:08:41,630 if you are able to find the right most node at this level, you can assume that all the notes the left 121 00:08:41,630 --> 00:08:49,940 exist, which means that if you are able to figure out what number from left to right this node is, 122 00:08:50,300 --> 00:08:53,990 you could immediately tell how many nodes are in this level. 123 00:08:54,680 --> 00:09:00,770 The trick, though, is figuring out that this is the right note to look for, because once again, 124 00:09:00,920 --> 00:09:03,830 we are starting from the context of this root node. 125 00:09:04,370 --> 00:09:10,250 At this point, we have no idea how many nodes are down here, but we don't know the maximum number 126 00:09:10,250 --> 00:09:12,200 of nodes that it could possibly be. 127 00:09:13,190 --> 00:09:18,920 We also know that the minimum number of note that it could possibly be as well, so these bits of knowledge 128 00:09:18,920 --> 00:09:21,540 combined might be able to help you figure it out. 129 00:09:22,220 --> 00:09:26,810 I will give you another hint, which is the fact that you need to do this in a given time and you're 130 00:09:26,810 --> 00:09:28,730 essentially searching for a note. 131 00:09:28,730 --> 00:09:33,560 And I don't want you to be locked into the idea that you're searching in a binary tree structure, at 132 00:09:33,560 --> 00:09:40,160 least for the idea what search can we perform in log and time? 133 00:09:41,070 --> 00:09:45,630 We already know that the only search that can perform and log in time is binary search. 134 00:09:45,780 --> 00:09:50,910 So how do we perform binary search on this structure to get this value? 135 00:09:51,090 --> 00:09:52,060 That's my challenge to you. 136 00:09:52,230 --> 00:09:53,720 You don't have to be able to do it right away. 137 00:09:53,730 --> 00:09:58,050 I just want you to think about it and really fight with it to figure it out, because there's a lot 138 00:09:58,050 --> 00:10:00,930 of steps here in order to get this to work with binary search. 139 00:10:01,050 --> 00:10:02,520 But that's the big hint to you. 140 00:10:03,030 --> 00:10:07,020 Not only do you have to determine the value that you're looking for, but you also have to determine 141 00:10:07,020 --> 00:10:11,190 how to verify if that value exists from the route. 142 00:10:11,400 --> 00:10:16,410 You need to combine those two things together in order to come up with an optimal solution that all 143 00:10:16,410 --> 00:10:18,340 performs in log and time. 144 00:10:18,570 --> 00:10:19,860 So that's my challenge to you. 145 00:10:20,190 --> 00:10:24,990 Try and see if you can figure out at least parts of it, and I'll show you how we can do it in the next 146 00:10:24,990 --> 00:10:25,320 video.