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.

