Hi, everyone.
So in this video, we are going to solve this question.
Count the number of nodes present in a binary.
So this is a binary tree and we have to return.
How many notes are present in this binary tree?
So there are total nine nodes, so which would be nine.
Similarly for this tree, there are total six nodes, so the output should be six.
So this question is very simple.
So how do we realize our tree?
We will always have a tree like this.
This is my.
This is the left subtree and this is the right subtree.
So we can easily solve this problem with the help of recursion.
So what I will do, I will call that equation on this tree.
So this tree will return me how many nodes at present.
Similarly, I will call the function count node on this.
Right.
So this tree will return me how many notes are present.
And then finally what I will do.
So I will add this node plus these nodes and I will add plus one because of the root node.
That will be my answer.
So for example, for this tree, this is my left Sabry.
And this is my right subtree.
So this story will return on Saturday that they are not present and this jury will return the answer
one, two, three, four and five.
So this jury will not survive.
Then I will add three plus five, which is eight, and I will add plus one.
Due to the amounts, it will be three plus five left value plus the right number of not present and
left number of notes presented.
Right, plus one.
OK, so what we have to do, what will be our answer.
So I will answer will be the number of nodes present in the left.
So left notes, number of notes presently left plus the number of nodes presenting right three right
Sabry and plus one because of the route node.
So this will be my answer.
So how it will work, so let's take a small example, let's take this example, so when so when will
call on two do we'll call on four for on the left.
Now, let's hope it does not exist, so it will return zero.
Similarly for I will call and write.
It will return zero.
And what is our answer.
Left notes which is zero right notes which is zero and plus one.
So I will turn develop zero zero plus one.
So four will return one then two will call on five.
So five will call on left and right.
They will return zero then zero zero plus one.
So five will return one then.
This is one for two left.
This one right is also one and plus one due to the rule and also two and three.
Now one will call on three so three will call on six.
Six will call on left and right and they both will return zero, then six will return one and three
will return this one.
So three will also call and write and write does not exist.
So from right.
Three is getting zero and from left to is getting one.
So when plus zero and plus one due to three so three will return to so for one we are getting three
from left, we are getting two from right.
So three plus two, five and plus one.
So the output will be six which is the right answer.
OK, so what is the best case.
So this case is very simple.
If the route is null, if route does not exist, if trees empty, then how many number of roads are
present?
So I will return zero zero and also president if the rotational.
Otherwise what is my answer?
So I will simply return this number of nodes present and left.
So I will return the number of nodes present in left number of nodes present and right plus one.
So that is all about this question.
So this question is basically present only told.
So the name of this question is basically count completely node.
So for Destry the output is six because there are six node present industry.
So let's write the code.
So that is integer and I am taking root as input.
So let's complete this function.
So what is the best case?
So best case is if fruit if tree does not exist.
Then how many nodes that zero nodes represent?
So I will return zero otherwise, as discussed, what we need to do, so I will return the number of
nodes present and left, number of nodes presented right.
Plus one.
So I will return the number of present and left, so call this function count node and I will give it.
So I'm calling this function count node and I am giving it the left subtree, so it will give me how
many orders are President Left Subtree, then I will call this function on the right.
So I will give right and plus one due to root.
So how it is working.
So I'm counting how many nodes are presently left separate.
So what is the property of this function.
It take three years input and it will tell me how many notes are present.
So this will return.
How many roads are present in the left subtree.
So left node this will be how many nodes are present in the right.
So this is right node and plus one due to the root node.
And you can see we are doing exactly the same.
So we are doing exactly the same left node plus right node and plus one.
So left notes, right notes and plus one, so let's have a code and then we will try to submit our code.
So firstly, does a novel called.
So our court is correct.
Now, let's try to sum it up.
Good.
So basically, our gold got accepted to have a gold is correct.
So now let's discuss the time and the space complexity of our solution.
So what is the time and the space complexity?
So for this, see if this is my three, one, two, three and four.
Since we have to go through each and every note, so since we will go through each and every node,
so the time complexity will be big, often relative to the number of nodes present in nearby Nutri.
And what is the space complexity?
So how will the stack look like?
So basically this one will call on two.
We will call on three table column for so one, two, three and four and similarly four.
I will call on left and right.
So basically in the worst case, space complexity will be big often.
So this is the time and the space complexity of our solution.
So this is it from this video.
I will see you in the next one.