1 00:00:01,000 --> 00:00:01,640 Hi, everyone. 2 00:00:01,660 --> 00:00:08,470 So in this video, we are going to solve this question, find the maximum depth of a binary tree, OK, 3 00:00:08,860 --> 00:00:13,450 find the maximum depth of a binary tree that either way to solve this equation, the better way to say 4 00:00:13,450 --> 00:00:17,020 this question is basically find the height of a binary tree. 5 00:00:17,050 --> 00:00:17,410 OK. 6 00:00:18,470 --> 00:00:21,110 We have to find the height of a binary tree. 7 00:00:21,260 --> 00:00:23,640 OK, so let us consider some example. 8 00:00:23,660 --> 00:00:27,170 So if this is the military now, what is the height? 9 00:00:27,740 --> 00:00:29,330 So basically, this is the root node. 10 00:00:31,270 --> 00:00:38,260 OK, so this is level one, this is level two, and this is level three, OK, since they are a maximum 11 00:00:38,260 --> 00:00:38,890 three levels. 12 00:00:39,010 --> 00:00:44,830 So the height of this binded is basically three height or you can say max depth. 13 00:00:45,010 --> 00:00:46,650 OK, Max Baptistery. 14 00:00:47,110 --> 00:00:50,700 So what is the what is the definition? 15 00:00:50,890 --> 00:00:57,640 So definition is basically the distance between the number of nodes, between the root node and the 16 00:00:57,640 --> 00:00:59,650 farthest node from the root. 17 00:00:59,680 --> 00:01:01,110 OK, I have to count. 18 00:01:01,330 --> 00:01:04,360 So four and five, so four and five. 19 00:01:05,080 --> 00:01:08,320 These are the farthest node from the root node. 20 00:01:09,460 --> 00:01:12,430 And what we will do, we will count the number of nodes between them. 21 00:01:12,910 --> 00:01:15,950 OK, so this is not one this is Nordal or against. 22 00:01:16,020 --> 00:01:18,010 This is not tree or this is also not tree. 23 00:01:18,500 --> 00:01:18,850 OK. 24 00:01:20,290 --> 00:01:26,920 Now for this military, what is the height or the maximum depth, so it is simply to this level one, 25 00:01:26,920 --> 00:01:29,290 this is level two, level one and level two. 26 00:01:29,620 --> 00:01:32,140 So the depth you can see is two. 27 00:01:32,950 --> 00:01:33,970 So I'm calling levels. 28 00:01:33,970 --> 00:01:38,050 You can say depth is one Baptista baptistery, OK? 29 00:01:39,150 --> 00:01:40,860 So now let us consider this example. 30 00:01:40,890 --> 00:01:47,130 So this is the root node, so this is that one, this is that two and this is that three. 31 00:01:47,370 --> 00:01:48,390 There is any other node. 32 00:01:48,420 --> 00:01:49,750 So this is that four. 33 00:01:50,130 --> 00:01:54,260 So the hide or you can say the maximum depth of this binary is basically four. 34 00:01:54,660 --> 00:01:56,090 Let's call it node five. 35 00:01:56,370 --> 00:01:58,320 So the depth or the height is four. 36 00:01:58,380 --> 00:01:58,740 OK. 37 00:02:00,080 --> 00:02:01,590 Now, let us consider this example. 38 00:02:01,620 --> 00:02:02,550 So this is the route north. 39 00:02:02,990 --> 00:02:09,800 So this is Daptone or you can say one depth to that three depth, four and five. 40 00:02:09,889 --> 00:02:13,700 OK, so six is the farthest north from the route node. 41 00:02:15,050 --> 00:02:20,300 And if you want to find out the height, what we will do, we will count the node to the node when this 42 00:02:20,300 --> 00:02:20,660 is No. 43 00:02:20,660 --> 00:02:21,060 Two. 44 00:02:21,110 --> 00:02:22,020 This is not three. 45 00:02:22,250 --> 00:02:23,270 This is not four. 46 00:02:23,270 --> 00:02:24,410 And this is node five. 47 00:02:24,590 --> 00:02:28,330 OK, so that's why the height is basically is five. 48 00:02:28,340 --> 00:02:31,040 Or you can say that makes Adap.tv makes Leptis five. 49 00:02:31,920 --> 00:02:34,670 OK, so I hope you understood the question. 50 00:02:35,610 --> 00:02:37,790 So basically, their definition is very simple. 51 00:02:39,340 --> 00:02:45,730 The maximum depth is basically the number of Naude along the longest path from the route to the farthest 52 00:02:45,730 --> 00:02:46,000 north. 53 00:02:46,030 --> 00:02:49,900 OK, so this is a little difficult to understand with the help of example. 54 00:02:49,900 --> 00:02:51,400 We can understand it inevitably. 55 00:02:51,460 --> 00:02:51,790 OK. 56 00:02:52,740 --> 00:02:59,040 Now, the question is, we are given a binary, OK, so the question is very simple. 57 00:02:59,040 --> 00:03:04,260 We are given a binary tree and we have to write the code for finding the maximum depth or you can see 58 00:03:04,260 --> 00:03:05,690 the height of the binary. 59 00:03:06,780 --> 00:03:08,630 So the function signature is very simple. 60 00:03:08,910 --> 00:03:14,010 It will be integer to the name of the function is eight and it will take root as input. 61 00:03:14,220 --> 00:03:14,580 OK. 62 00:03:15,660 --> 00:03:19,210 Now I have to write the code, so this is very simple. 63 00:03:19,980 --> 00:03:22,220 OK, so what I will do, very simple approach. 64 00:03:22,230 --> 00:03:25,490 This is Route A. This is the left subtree. 65 00:03:26,280 --> 00:03:27,660 This is the right subtree. 66 00:03:29,860 --> 00:03:36,220 OK, so what is the work of dysfunction hate, so this hate function takes root as input and it will 67 00:03:36,220 --> 00:03:38,090 return me the hate simple. 68 00:03:38,320 --> 00:03:41,320 So what I will do, find the height of the left subtree. 69 00:03:41,860 --> 00:03:43,850 Find the height of the eye. 70 00:03:43,870 --> 00:03:50,980 It's a pretty take the maximum of the height of the left and right subtree and add plus one. 71 00:03:50,980 --> 00:03:52,600 Right plus one because the root. 72 00:03:53,200 --> 00:03:57,800 OK, so what I will do I will find the height of the left separately. 73 00:03:58,030 --> 00:04:00,760 OK, so I will call this function height. 74 00:04:01,390 --> 00:04:03,740 I will give it rumold so sorry. 75 00:04:03,790 --> 00:04:04,540 Left subtree. 76 00:04:04,930 --> 00:04:10,960 So find the height of the left subtree then this height function will take right subtree. 77 00:04:10,960 --> 00:04:13,330 So it will return me the height of right subtree. 78 00:04:14,410 --> 00:04:18,190 And then after finding the height of Cyprien right. 79 00:04:18,550 --> 00:04:24,100 I will take the maximum of these two and I will add plus one plus one is due to rule. 80 00:04:25,160 --> 00:04:28,330 OK, let's take some example to understand it better be OK. 81 00:04:29,500 --> 00:04:31,540 So let us take some example. 82 00:04:33,620 --> 00:04:37,880 So suppose this is the tree for five, seven, six. 83 00:04:38,930 --> 00:04:40,780 Two and three. 84 00:04:41,620 --> 00:04:43,330 OK, so this is the root node. 85 00:04:44,880 --> 00:04:50,400 So what I'm saying here is find the height of the left debris, so the height of legs, approximately 86 00:04:50,400 --> 00:04:51,840 one, two, three. 87 00:04:52,030 --> 00:04:58,980 So the height of trees, one, find the height, the height of this tree, find the height of the right 88 00:04:58,980 --> 00:04:59,210 spot. 89 00:04:59,400 --> 00:05:02,480 So this is one depth one depth two. 90 00:05:02,790 --> 00:05:03,550 So this is two. 91 00:05:03,870 --> 00:05:08,370 OK, so four left subtree height is three four right subtree. 92 00:05:08,370 --> 00:05:09,240 The height is two. 93 00:05:09,430 --> 00:05:12,930 I will take the maximum of left side, left and right. 94 00:05:12,930 --> 00:05:13,180 Right. 95 00:05:13,200 --> 00:05:15,680 Which is basically three oak trees that then two. 96 00:05:15,990 --> 00:05:22,410 So three and I will add plus one plus one is due to not so it on several before. 97 00:05:22,490 --> 00:05:26,990 OK, you can see how good it is for forensics, the distance between them. 98 00:05:27,000 --> 00:05:29,670 So this is not one or two or three and four. 99 00:05:30,330 --> 00:05:32,180 OK, very simple approach. 100 00:05:33,000 --> 00:05:34,830 OK, this is very, very simple approach. 101 00:05:35,220 --> 00:05:41,040 Find the height of the left debris, find the height of the right subtree, take the maximum of them 102 00:05:41,040 --> 00:05:42,420 and add plus one. 103 00:05:43,910 --> 00:05:44,300 OK. 104 00:05:45,560 --> 00:05:49,320 Very, very simple, let us take one more example to understand it better. 105 00:05:49,340 --> 00:05:49,670 OK? 106 00:05:51,390 --> 00:05:58,410 Now, this is the example we need to find the height of the debris, so height of the trees, one, 107 00:05:58,770 --> 00:06:01,350 find the height of the right debris, which is zero. 108 00:06:01,770 --> 00:06:04,520 OK, you will take the maximum of one and zero. 109 00:06:04,530 --> 00:06:08,110 So it will be one and then I will add plus one due to the root node. 110 00:06:08,280 --> 00:06:12,690 So basically the height will be two four distri, which is correct. 111 00:06:13,170 --> 00:06:13,600 OK. 112 00:06:13,890 --> 00:06:15,000 So very, very simple. 113 00:06:16,130 --> 00:06:19,700 Mix of height of lift, height of right. 114 00:06:20,790 --> 00:06:26,700 I will take the maximum height of height of rights and I will add plus one, this plus one is due to 115 00:06:26,700 --> 00:06:28,320 root node, OK. 116 00:06:28,710 --> 00:06:29,370 Very simple. 117 00:06:29,880 --> 00:06:30,540 Understood. 118 00:06:30,720 --> 00:06:31,710 Now let's it called. 119 00:06:33,190 --> 00:06:35,500 OK, the name of the function is Max Depth. 120 00:06:36,520 --> 00:06:40,570 It is taking root as input and I have to return the hate or accept. 121 00:06:40,600 --> 00:06:42,820 OK, so first of all, the base. 122 00:06:43,390 --> 00:06:50,590 So if personal basically does not exist, OK, if the tree does not exist, then what will be the hate? 123 00:06:50,590 --> 00:06:53,200 The hate will be zero if it is not there. 124 00:06:53,380 --> 00:06:54,040 It will be zero. 125 00:06:54,040 --> 00:06:56,130 If they did not exist, it will be zero. 126 00:06:56,980 --> 00:06:59,500 Now let us find out the mix depth. 127 00:06:59,580 --> 00:07:03,010 You can say the height of the are so mixed depth. 128 00:07:04,810 --> 00:07:08,340 Give me the height of the left subtree. 129 00:07:08,380 --> 00:07:11,980 So now I know the max depth of the right of the left. 130 00:07:13,030 --> 00:07:16,750 Now let us try to find out the max depth of the. 131 00:07:20,640 --> 00:07:21,810 Right subtree, OK? 132 00:07:23,450 --> 00:07:29,780 So basically mixed tonight, the voters seem OK, they both seem so I'm writing here. 133 00:07:33,560 --> 00:07:36,410 Max, depth and height, they both have slim. 134 00:07:41,570 --> 00:07:48,500 So I know the extent of the legendary I know the height or the depth of the debris, but I have to do 135 00:07:48,500 --> 00:07:51,620 I have to take the maximum of these two and I have to add a plus one. 136 00:07:52,490 --> 00:07:55,250 So Mix's and build function in C++. 137 00:07:56,510 --> 00:08:04,110 The maximum of height of right, and you will let a person because of duty, road and Dritan. 138 00:08:04,200 --> 00:08:10,190 OK, so take the mics off left and right and add plus one and then return. 139 00:08:10,280 --> 00:08:10,610 OK. 140 00:08:14,790 --> 00:08:16,290 Now, let us our good. 141 00:08:20,420 --> 00:08:25,010 OK, so our code is working fine now let us right in our code on very small example. 142 00:08:28,290 --> 00:08:33,330 So let us take this example, one, two, three, and here I have four. 143 00:08:33,360 --> 00:08:35,039 OK, so what should be the answer? 144 00:08:35,070 --> 00:08:38,190 So I should be basically the height of this tree should be tree. 145 00:08:38,500 --> 00:08:39,870 OK, that makes dentistry. 146 00:08:40,230 --> 00:08:41,039 So what will happen? 147 00:08:42,169 --> 00:08:47,660 When when we call on left, give me the heart of the left, who will call on right to give me the right 148 00:08:47,660 --> 00:08:53,090 of their three will go on the left and basically left SNL, so it will return zero. 149 00:08:54,190 --> 00:08:55,580 Then three will call on, right? 150 00:08:55,600 --> 00:09:02,080 Give me the height of rights, so riot will return zero, then I will take the maximum of zero and zero, 151 00:09:02,410 --> 00:09:04,510 which is zero, and I will add plus one. 152 00:09:04,750 --> 00:09:08,510 OK, so three will return one to two. 153 00:09:09,190 --> 00:09:11,810 OK, so two colon left now. 154 00:09:11,820 --> 00:09:12,610 Two colon. 155 00:09:12,610 --> 00:09:12,940 Right. 156 00:09:13,420 --> 00:09:15,630 So give me the height of right height. 157 00:09:16,030 --> 00:09:17,640 Basically it will be right there. 158 00:09:17,780 --> 00:09:18,580 It does not exist. 159 00:09:18,790 --> 00:09:20,080 So it will return zero. 160 00:09:20,260 --> 00:09:22,020 OK, it will return zero. 161 00:09:22,720 --> 00:09:27,460 Then I have to take the mix off left subtree, which is one right subtree, which is zero. 162 00:09:27,610 --> 00:09:29,730 So one zero, which is maximum one. 163 00:09:29,980 --> 00:09:31,930 And I have to return one plus one. 164 00:09:31,990 --> 00:09:35,500 OK, so this two will return one. 165 00:09:36,540 --> 00:09:42,760 So it will return height to OK, no one has called on left, no one will call on right. 166 00:09:43,680 --> 00:09:47,070 Give me the height of right subtree forwell call left. 167 00:09:47,190 --> 00:09:48,180 Give me the height of Lurdes. 168 00:09:48,600 --> 00:09:49,910 Left separate does not exist. 169 00:09:49,920 --> 00:09:51,990 It will return zero to 10 zero. 170 00:09:52,410 --> 00:09:54,580 Then it will go on right right up. 171 00:09:54,630 --> 00:09:55,470 It does not exist. 172 00:09:55,470 --> 00:09:58,800 So it will return zero maximov zero zero. 173 00:09:58,800 --> 00:09:59,520 It will be zero. 174 00:09:59,790 --> 00:10:00,930 Then return plus one. 175 00:10:01,300 --> 00:10:02,250 OK Max. 176 00:10:02,430 --> 00:10:03,330 And plus one. 177 00:10:03,810 --> 00:10:05,130 So four will return when. 178 00:10:06,750 --> 00:10:12,220 To the root node now, root root node left is returning to right is returning one. 179 00:10:12,360 --> 00:10:14,980 So take the maximum of two and one, it will be two. 180 00:10:15,240 --> 00:10:18,350 So finally, it will return to plus one, which is three. 181 00:10:18,390 --> 00:10:20,350 OK, and three is our answer. 182 00:10:20,670 --> 00:10:22,410 So that's how this code is working. 183 00:10:22,440 --> 00:10:24,930 OK, now let's discuss the time complexity. 184 00:10:24,930 --> 00:10:27,210 Since we are going through each and every note time. 185 00:10:27,210 --> 00:10:29,040 Complexity is big often, OK. 186 00:10:30,440 --> 00:10:35,930 Very simple and similarly, the space complexity will be big, often in the worst case, OK, in the 187 00:10:35,930 --> 00:10:36,920 worst case, what will happen? 188 00:10:36,920 --> 00:10:40,970 Mitry is basically not a ballistically it is a one sided tree. 189 00:10:41,000 --> 00:10:44,820 OK, so suppose the tree is basically four, three and seven. 190 00:10:46,010 --> 00:10:47,240 So in this case, what will happen? 191 00:10:48,680 --> 00:10:53,780 So for will call on the left to find the right tree, will call on the left supplier to find out. 192 00:10:53,810 --> 00:11:00,130 So basically if there are three nodes in the military, so there are so the stakes will be three. 193 00:11:00,170 --> 00:11:03,920 OK, so that's why in the worst case, in the case of a good tree, OK. 194 00:11:05,550 --> 00:11:13,830 This is a good story, so so in the worst case, that is in the case of as good a tree, my time complexity 195 00:11:13,830 --> 00:11:14,850 will be big often. 196 00:11:14,880 --> 00:11:19,260 OK, so time and space, both are big often. 197 00:11:20,470 --> 00:11:26,020 And the code is very simple, only three to four lines of code, OK, only these three lines of code. 198 00:11:26,300 --> 00:11:26,570 OK. 199 00:11:28,100 --> 00:11:28,550 Thank you.