Hi, everyone.
So in this video, we are going to solve this question, find the maximum depth of a binary tree, OK,
find the maximum depth of a binary tree that either way to solve this equation, the better way to say
this question is basically find the height of a binary tree.
OK.
We have to find the height of a binary tree.
OK, so let us consider some example.
So if this is the military now, what is the height?
So basically, this is the root node.
OK, so this is level one, this is level two, and this is level three, OK, since they are a maximum
three levels.
So the height of this binded is basically three height or you can say max depth.
OK, Max Baptistery.
So what is the what is the definition?
So definition is basically the distance between the number of nodes, between the root node and the
farthest node from the root.
OK, I have to count.
So four and five, so four and five.
These are the farthest node from the root node.
And what we will do, we will count the number of nodes between them.
OK, so this is not one this is Nordal or against.
This is not tree or this is also not tree.
OK.
Now for this military, what is the height or the maximum depth, so it is simply to this level one,
this is level two, level one and level two.
So the depth you can see is two.
So I'm calling levels.
You can say depth is one Baptista baptistery, OK?
So now let us consider this example.
So this is the root node, so this is that one, this is that two and this is that three.
There is any other node.
So this is that four.
So the hide or you can say the maximum depth of this binary is basically four.
Let's call it node five.
So the depth or the height is four.
OK.
Now, let us consider this example.
So this is the route north.
So this is Daptone or you can say one depth to that three depth, four and five.
OK, so six is the farthest north from the route node.
And if you want to find out the height, what we will do, we will count the node to the node when this
is No.
Two.
This is not three.
This is not four.
And this is node five.
OK, so that's why the height is basically is five.
Or you can say that makes Adap.tv makes Leptis five.
OK, so I hope you understood the question.
So basically, their definition is very simple.
The maximum depth is basically the number of Naude along the longest path from the route to the farthest
north.
OK, so this is a little difficult to understand with the help of example.
We can understand it inevitably.
OK.
Now, the question is, we are given a binary, OK, so the question is very simple.
We are given a binary tree and we have to write the code for finding the maximum depth or you can see
the height of the binary.
So the function signature is very simple.
It will be integer to the name of the function is eight and it will take root as input.
OK.
Now I have to write the code, so this is very simple.
OK, so what I will do, very simple approach.
This is Route A. This is the left subtree.
This is the right subtree.
OK, so what is the work of dysfunction hate, so this hate function takes root as input and it will
return me the hate simple.
So what I will do, find the height of the left subtree.
Find the height of the eye.
It's a pretty take the maximum of the height of the left and right subtree and add plus one.
Right plus one because the root.
OK, so what I will do I will find the height of the left separately.
OK, so I will call this function height.
I will give it rumold so sorry.
Left subtree.
So find the height of the left subtree then this height function will take right subtree.
So it will return me the height of right subtree.
And then after finding the height of Cyprien right.
I will take the maximum of these two and I will add plus one plus one is due to rule.
OK, let's take some example to understand it better be OK.
So let us take some example.
So suppose this is the tree for five, seven, six.
Two and three.
OK, so this is the root node.
So what I'm saying here is find the height of the left debris, so the height of legs, approximately
one, two, three.
So the height of trees, one, find the height, the height of this tree, find the height of the right
spot.
So this is one depth one depth two.
So this is two.
OK, so four left subtree height is three four right subtree.
The height is two.
I will take the maximum of left side, left and right.
Right.
Which is basically three oak trees that then two.
So three and I will add plus one plus one is due to not so it on several before.
OK, you can see how good it is for forensics, the distance between them.
So this is not one or two or three and four.
OK, very simple approach.
OK, this is very, very simple approach.
Find the height of the left debris, find the height of the right subtree, take the maximum of them
and add plus one.
OK.
Very, very simple, let us take one more example to understand it better.
OK?
Now, this is the example we need to find the height of the debris, so height of the trees, one,
find the height of the right debris, which is zero.
OK, you will take the maximum of one and zero.
So it will be one and then I will add plus one due to the root node.
So basically the height will be two four distri, which is correct.
OK.
So very, very simple.
Mix of height of lift, height of right.
I will take the maximum height of height of rights and I will add plus one, this plus one is due to
root node, OK.
Very simple.
Understood.
Now let's it called.
OK, the name of the function is Max Depth.
It is taking root as input and I have to return the hate or accept.
OK, so first of all, the base.
So if personal basically does not exist, OK, if the tree does not exist, then what will be the hate?
The hate will be zero if it is not there.
It will be zero.
If they did not exist, it will be zero.
Now let us find out the mix depth.
You can say the height of the are so mixed depth.
Give me the height of the left subtree.
So now I know the max depth of the right of the left.
Now let us try to find out the max depth of the.
Right subtree, OK?
So basically mixed tonight, the voters seem OK, they both seem so I'm writing here.
Max, depth and height, they both have slim.
So I know the extent of the legendary I know the height or the depth of the debris, but I have to do
I have to take the maximum of these two and I have to add a plus one.
So Mix's and build function in C++.
The maximum of height of right, and you will let a person because of duty, road and Dritan.
OK, so take the mics off left and right and add plus one and then return.
OK.
Now, let us our good.
OK, so our code is working fine now let us right in our code on very small example.
So let us take this example, one, two, three, and here I have four.
OK, so what should be the answer?
So I should be basically the height of this tree should be tree.
OK, that makes dentistry.
So what will happen?
When when we call on left, give me the heart of the left, who will call on right to give me the right
of their three will go on the left and basically left SNL, so it will return zero.
Then three will call on, right?
Give me the height of rights, so riot will return zero, then I will take the maximum of zero and zero,
which is zero, and I will add plus one.
OK, so three will return one to two.
OK, so two colon left now.
Two colon.
Right.
So give me the height of right height.
Basically it will be right there.
It does not exist.
So it will return zero.
OK, it will return zero.
Then I have to take the mix off left subtree, which is one right subtree, which is zero.
So one zero, which is maximum one.
And I have to return one plus one.
OK, so this two will return one.
So it will return height to OK, no one has called on left, no one will call on right.
Give me the height of right subtree forwell call left.
Give me the height of Lurdes.
Left separate does not exist.
It will return zero to 10 zero.
Then it will go on right right up.
It does not exist.
So it will return zero maximov zero zero.
It will be zero.
Then return plus one.
OK Max.
And plus one.
So four will return when.
To the root node now, root root node left is returning to right is returning one.
So take the maximum of two and one, it will be two.
So finally, it will return to plus one, which is three.
OK, and three is our answer.
So that's how this code is working.
OK, now let's discuss the time complexity.
Since we are going through each and every note time.
Complexity is big often, OK.
Very simple and similarly, the space complexity will be big, often in the worst case, OK, in the
worst case, what will happen?
Mitry is basically not a ballistically it is a one sided tree.
OK, so suppose the tree is basically four, three and seven.
So in this case, what will happen?
So for will call on the left to find the right tree, will call on the left supplier to find out.
So basically if there are three nodes in the military, so there are so the stakes will be three.
OK, so that's why in the worst case, in the case of a good tree, OK.
This is a good story, so so in the worst case, that is in the case of as good a tree, my time complexity
will be big often.
OK, so time and space, both are big often.
And the code is very simple, only three to four lines of code, OK, only these three lines of code.
OK.
Thank you.