1 00:00:01,560 --> 00:00:02,260 Hi, everyone. 2 00:00:02,280 --> 00:00:04,760 So in this video, we are going to solve this question. 3 00:00:04,770 --> 00:00:07,480 Count the number of nodes present in a binary. 4 00:00:07,770 --> 00:00:10,200 So this is a binary tree and we have to return. 5 00:00:10,200 --> 00:00:12,270 How many notes are present in this binary tree? 6 00:00:12,480 --> 00:00:15,380 So there are total nine nodes, so which would be nine. 7 00:00:15,750 --> 00:00:20,130 Similarly for this tree, there are total six nodes, so the output should be six. 8 00:00:20,940 --> 00:00:22,450 So this question is very simple. 9 00:00:22,620 --> 00:00:24,320 So how do we realize our tree? 10 00:00:24,600 --> 00:00:26,510 We will always have a tree like this. 11 00:00:26,520 --> 00:00:27,030 This is my. 12 00:00:27,570 --> 00:00:30,600 This is the left subtree and this is the right subtree. 13 00:00:30,780 --> 00:00:33,220 So we can easily solve this problem with the help of recursion. 14 00:00:33,390 --> 00:00:36,730 So what I will do, I will call that equation on this tree. 15 00:00:36,780 --> 00:00:39,990 So this tree will return me how many nodes at present. 16 00:00:40,020 --> 00:00:42,720 Similarly, I will call the function count node on this. 17 00:00:42,720 --> 00:00:43,020 Right. 18 00:00:43,680 --> 00:00:46,550 So this tree will return me how many notes are present. 19 00:00:46,680 --> 00:00:48,240 And then finally what I will do. 20 00:00:48,240 --> 00:00:52,950 So I will add this node plus these nodes and I will add plus one because of the root node. 21 00:00:53,550 --> 00:00:54,630 That will be my answer. 22 00:00:55,020 --> 00:00:58,350 So for example, for this tree, this is my left Sabry. 23 00:00:59,240 --> 00:01:01,130 And this is my right subtree. 24 00:01:03,220 --> 00:01:08,710 So this story will return on Saturday that they are not present and this jury will return the answer 25 00:01:08,710 --> 00:01:10,340 one, two, three, four and five. 26 00:01:10,540 --> 00:01:12,060 So this jury will not survive. 27 00:01:12,070 --> 00:01:16,120 Then I will add three plus five, which is eight, and I will add plus one. 28 00:01:16,120 --> 00:01:21,910 Due to the amounts, it will be three plus five left value plus the right number of not present and 29 00:01:21,910 --> 00:01:23,270 left number of notes presented. 30 00:01:23,320 --> 00:01:24,190 Right, plus one. 31 00:01:24,400 --> 00:01:27,210 OK, so what we have to do, what will be our answer. 32 00:01:27,370 --> 00:01:30,910 So I will answer will be the number of nodes present in the left. 33 00:01:31,150 --> 00:01:38,000 So left notes, number of notes presently left plus the number of nodes presenting right three right 34 00:01:38,010 --> 00:01:40,690 Sabry and plus one because of the route node. 35 00:01:40,840 --> 00:01:42,120 So this will be my answer. 36 00:01:43,250 --> 00:01:49,270 So how it will work, so let's take a small example, let's take this example, so when so when will 37 00:01:49,280 --> 00:01:52,920 call on two do we'll call on four for on the left. 38 00:01:52,940 --> 00:01:55,430 Now, let's hope it does not exist, so it will return zero. 39 00:01:55,580 --> 00:01:57,110 Similarly for I will call and write. 40 00:01:57,110 --> 00:01:58,100 It will return zero. 41 00:01:58,250 --> 00:01:59,320 And what is our answer. 42 00:01:59,330 --> 00:02:03,490 Left notes which is zero right notes which is zero and plus one. 43 00:02:03,620 --> 00:02:06,260 So I will turn develop zero zero plus one. 44 00:02:06,270 --> 00:02:09,229 So four will return one then two will call on five. 45 00:02:09,440 --> 00:02:11,360 So five will call on left and right. 46 00:02:11,360 --> 00:02:14,850 They will return zero then zero zero plus one. 47 00:02:14,870 --> 00:02:16,700 So five will return one then. 48 00:02:16,700 --> 00:02:18,540 This is one for two left. 49 00:02:18,540 --> 00:02:22,850 This one right is also one and plus one due to the rule and also two and three. 50 00:02:23,600 --> 00:02:26,330 Now one will call on three so three will call on six. 51 00:02:26,540 --> 00:02:32,240 Six will call on left and right and they both will return zero, then six will return one and three 52 00:02:32,240 --> 00:02:33,260 will return this one. 53 00:02:33,830 --> 00:02:36,410 So three will also call and write and write does not exist. 54 00:02:36,530 --> 00:02:37,440 So from right. 55 00:02:37,440 --> 00:02:40,270 Three is getting zero and from left to is getting one. 56 00:02:40,400 --> 00:02:46,880 So when plus zero and plus one due to three so three will return to so for one we are getting three 57 00:02:46,880 --> 00:02:49,210 from left, we are getting two from right. 58 00:02:49,220 --> 00:02:51,350 So three plus two, five and plus one. 59 00:02:51,530 --> 00:02:54,170 So the output will be six which is the right answer. 60 00:02:54,470 --> 00:02:56,540 OK, so what is the best case. 61 00:02:57,950 --> 00:02:59,450 So this case is very simple. 62 00:02:59,450 --> 00:03:06,050 If the route is null, if route does not exist, if trees empty, then how many number of roads are 63 00:03:06,050 --> 00:03:06,460 present? 64 00:03:06,680 --> 00:03:09,800 So I will return zero zero and also president if the rotational. 65 00:03:10,190 --> 00:03:12,070 Otherwise what is my answer? 66 00:03:12,350 --> 00:03:16,460 So I will simply return this number of nodes present and left. 67 00:03:16,460 --> 00:03:21,140 So I will return the number of nodes present in left number of nodes present and right plus one. 68 00:03:21,590 --> 00:03:23,440 So that is all about this question. 69 00:03:23,630 --> 00:03:26,040 So this question is basically present only told. 70 00:03:26,330 --> 00:03:30,500 So the name of this question is basically count completely node. 71 00:03:30,650 --> 00:03:35,330 So for Destry the output is six because there are six node present industry. 72 00:03:35,540 --> 00:03:37,430 So let's write the code. 73 00:03:37,550 --> 00:03:41,090 So that is integer and I am taking root as input. 74 00:03:41,390 --> 00:03:42,890 So let's complete this function. 75 00:03:43,930 --> 00:03:45,040 So what is the best case? 76 00:03:45,670 --> 00:03:50,190 So best case is if fruit if tree does not exist. 77 00:03:51,530 --> 00:03:54,180 Then how many nodes that zero nodes represent? 78 00:03:54,200 --> 00:04:01,280 So I will return zero otherwise, as discussed, what we need to do, so I will return the number of 79 00:04:01,280 --> 00:04:04,100 nodes present and left, number of nodes presented right. 80 00:04:04,100 --> 00:04:04,700 Plus one. 81 00:04:06,520 --> 00:04:13,570 So I will return the number of present and left, so call this function count node and I will give it. 82 00:04:15,010 --> 00:04:21,279 So I'm calling this function count node and I am giving it the left subtree, so it will give me how 83 00:04:21,279 --> 00:04:27,300 many orders are President Left Subtree, then I will call this function on the right. 84 00:04:27,700 --> 00:04:31,530 So I will give right and plus one due to root. 85 00:04:31,780 --> 00:04:32,890 So how it is working. 86 00:04:33,130 --> 00:04:36,830 So I'm counting how many nodes are presently left separate. 87 00:04:36,960 --> 00:04:38,470 So what is the property of this function. 88 00:04:38,650 --> 00:04:42,380 It take three years input and it will tell me how many notes are present. 89 00:04:42,610 --> 00:04:43,690 So this will return. 90 00:04:43,870 --> 00:04:45,790 How many roads are present in the left subtree. 91 00:04:45,790 --> 00:04:49,720 So left node this will be how many nodes are present in the right. 92 00:04:50,110 --> 00:04:53,380 So this is right node and plus one due to the root node. 93 00:04:53,380 --> 00:04:56,010 And you can see we are doing exactly the same. 94 00:04:56,470 --> 00:05:00,460 So we are doing exactly the same left node plus right node and plus one. 95 00:05:02,930 --> 00:05:08,720 So left notes, right notes and plus one, so let's have a code and then we will try to submit our code. 96 00:05:11,700 --> 00:05:13,170 So firstly, does a novel called. 97 00:05:15,550 --> 00:05:16,810 So our court is correct. 98 00:05:16,840 --> 00:05:18,040 Now, let's try to sum it up. 99 00:05:18,120 --> 00:05:18,360 Good. 100 00:05:23,090 --> 00:05:26,630 So basically, our gold got accepted to have a gold is correct. 101 00:05:27,050 --> 00:05:30,590 So now let's discuss the time and the space complexity of our solution. 102 00:05:31,040 --> 00:05:32,950 So what is the time and the space complexity? 103 00:05:34,250 --> 00:05:38,000 So for this, see if this is my three, one, two, three and four. 104 00:05:39,260 --> 00:05:43,730 Since we have to go through each and every note, so since we will go through each and every node, 105 00:05:44,360 --> 00:05:49,280 so the time complexity will be big, often relative to the number of nodes present in nearby Nutri. 106 00:05:49,670 --> 00:05:51,420 And what is the space complexity? 107 00:05:51,800 --> 00:05:53,970 So how will the stack look like? 108 00:05:54,890 --> 00:05:58,150 So basically this one will call on two. 109 00:05:58,170 --> 00:06:03,330 We will call on three table column for so one, two, three and four and similarly four. 110 00:06:03,340 --> 00:06:04,490 I will call on left and right. 111 00:06:04,640 --> 00:06:08,170 So basically in the worst case, space complexity will be big often. 112 00:06:08,450 --> 00:06:11,420 So this is the time and the space complexity of our solution. 113 00:06:12,380 --> 00:06:13,830 So this is it from this video. 114 00:06:13,850 --> 00:06:15,110 I will see you in the next one.