Hi, everyone.
So in this video, we are going to cover the situation, find the minimum depth of a binary tree.
OK, so what is the meaning of minimum depth?
So it is basically the distance between the root node and the nearest leaf.
OK.
The distance between the road and the nearest cliff, so let us take an example.
So consider this example.
So basically, this is the route node.
OK, this is the route node.
And 15 is a leaf node.
Seven is a leaf node.
Nine is a leaf node.
So I have three leaf node.
OK, I have three leaf node.
This is the nearest leaf and also node one and not two.
So the minimum depth of this by Newton is basically two.
OK.
Now let us go through this example.
So this is the root node and this is the nearest leaf node.
OK, 52 is also a leaf node.
Seventy two is also a leaf node, but it is the nearest road you can see.
I have to find out the nearest leaf node, OK.
Now the distance basically.
So this is Neptun, this is that two and this is that tree.
OK, so the minimum depth for this binary trees, basically three.
Now let us consider this example.
OK, so this is the root node and this is the nearest leaf node.
One and seven are also leaf node, but five is the nearest leaf node.
So now let's find out the depth so that when that two and that tree.
So the minimum depth for this binary is basically three.
OK, so I hope you understood the question.
We have to find the minimum that OK, we have to find the minimum that offered by Nutri.
Now let us know.
Let us discuss how we can solve this question.
OK, so basically this question is nothing.
It is just the implementation of level of the traversal.
OK, so this question is basically.
The implementation of law and order traversal.
Now let's see how, OK, let us consider a big example, OK?
OK, so consider this as a reminder to consider this example now what is the newest leaf?
And also don't tease the nearest leaf node.
OK, so what we will do so we will do the level of the cells on the laboratory.
First I will visit this, then I will visit this.
Then I will visit this.
So basically that one, I will also order that daptone that to that tree and then I will visit this
level.
So this is level four or you can say that for now.
You can see I have a node.
So this is basically a relief note.
So it is a relief not so left and right is also.
So as soon as you encounter, then as soon as in control.
If not, we will return it.
So it's Leptis basically for to answer for this by nutri the minimum.
That is basically food.
OK, so what we have to do, our logic is very simple.
We will perform the law and order traversal.
We will perform the laboratory and while performing the level of the trial itself, we will also order
that, OK, I will also order that.
Now, as soon as when we are performing the lutrova.
So as soon as we encounter a leaf node, as soon as we encounter a leaf node, we will return the depth
value.
OK, so in this case, for this adaptive value.
So the minimum depth for this Binit is basically for.
Now, let us do an example, let us consider an example and let us perform the laboratory, Wortzel.
OK, so let us consider this example.
Now let us perform the level of the trials and so when we are performing LEVEL-HEADED Traversal, we
knew that.
Q Okay, so initially MICU will be empty.
Initially my will be empty.
OK, now what I will do so I will push the root node and it's left to lose its depth values basically.
And so I will push two things.
Sartwell is the root value and when is start depth.
Very simple.
Now, what I will do, our simple approach.
OK, so what I will do so pop different element.
Check so left exist, right exist, push them and their debit values basically do OK, so ablated up
to value, which is true, and Bush.
So I will push seven its debit values to I will push 51 its delta values basically to.
OK, now again, Bob, different element, so seven is different element, now check so left.
So first of all, I will adapt to adapt values basically three OK, so left exist.
Right exist.
Push them.
So eat them that value three.
I have nine and 12 is basically three.
OK, now again, but I will pop different elements of 51 and two, so I will update them to adapt to
a loose three.
OK, left exist.
No, right exist.
Yes.
So push seven.
And that values basically three.
So push seven and that values basically three.
OK, now again what Bob.
Different element eight and three.
So I will update adaptively it'll become four.
So check left exists.
Right.
Existant also pushpin.
That values for OK now a different element, main commentary, so I will update the to values or values
basically for now Jack left exists.
No right exists.
So Bush dual debit values basically for OK now pop different elements.
Seven commentary.
OK, so this is seven different element left exist.
No right exist.
No.
So basically this is a Leaford.
Left do not exist, right do not exist.
So what I will do, I will stop.
And what I said in my answer will be three, OK, my answer will be three.
I will stop as soon as we encounter a leaf node, and my answer will be basically that that will do
so, which is tree.
OK, so this is simple.
The driver said, OK, so this is the level of the traversal implementation problem.
OK, this is simply traversal implementation problem.
Now since you have understood the logic, so I think we can now write the call.
OK, so now let's write the code.
So before writing the code, now let us discuss what is the time and the space complexity.
So basically what to with the time complexity.
So again, this is simple, but I wasn't a big orphan and the space complexity also big often.
OK, so this is the time and the space complexity for this solution.
Now you can see yourself.
So basically the level of the traversal is basically iterative traversal.
OK.
Laboratory attitude reversal in the space complexities, this one, and where is the order preordained
Bulstrode reversal.
So in order to bring order and the poster traversal, so their time complexity is also this much, but
they are all recursive approach, OK?
They are all recursive approach.
So basically the laboratory, it uses glue, it uses glue as data structure and all these traversal
basically use stack.
I asked you to structure, OK, so this is the difference between the level reversals and all these
reversals.
OK, time, complexity and space complexity, they are the same.
So this is 881.
All these three are recursive.
It uses skill and it uses a stack, OK.
So now let's write the code for this problem.
OK, minimum adaptive ability.
So as you can see, I have to store two things inside the.
OK, I have to store two things inside the queue.
So let us construct the structure.
What you can see a class so I will construct a class.
Glass will contain two things the order value and basically the that.
OK, northern, that I have to say two things, OK?
So fostering two things, I have options, so what I can do, I can construct a bed or I can use the
bed or I can use I can construct my own bed.
So let us construct our own bed.
OK, so let's name it item.
So itemise store this item.
It will be stored now, it will contain two things.
First is the node.
So PNTR, let's call it not only.
And secondly, it will contain the depth, so depth will be in.
Now, what I will do.
So now let us complete this function return represented here and then put is basically a tree.
OK, so what I have to do again, the best case.
So basically if the root canal.
So Rudimental, that means the tree does not exist, so if tree does not exist.
So what will that mean?
That will be zero.
OK, now let us construct a Q.
So this time, I will not construct queue of Renauld that this will be wrong because I have to start
putting.
OK, so first two things.
I have constructed this structure.
So what I will write, so I will construct Q off two item.
OK, so this one item I'm constructing, Q of Q item, OK, so let's name it.
Q.
Now, let us construct a quantum.
So this item, let's name it, basically Q Guey, OK, so it will contain two things root and the depth
of root is basically one.
OK, now let us push the first element inside that.
So good.
Not push.
QE.
OK, QE.
So what I'm doing here is basically.
So what I have to do, I have to push the first element, OK, so I am pushing three trees, the particularly
the root element, so I have to push through, baptise one.
OK, so this is basically a item.
This is a great time, you can see this is a key item, the name is basically Kuai, you can name it
anything and I am pushing this item inside the queue.
OK, I am pushing this item inside the queue.
Now, let us start our laboratory traversal, OK, so I was standard cold for LEVEL-HEADED traversal.
So while the queue is not empty.
What we have to do, we have to find a leaf node.
OK, so let us get the first element, OK, so.
Item.
Let's call it first, let's call it friend.
OK, so this will be basically culotte friend.
And then we have to do culotte Bob.
OK, good.
OUTFRONT tonight, Bob.
So now let's find out, Donald.
So what is Donald?
So it is basically, let's call it north.
So this is basically so.
If.
OK, so what I will write, so this is f dot naude.
OK, so this one after a..
OK, after not and let us also find out depth that.
OK, so in depth.
So this is basically f dot net.
If not that, OK, now what I will also check whether this node check whether this node is leaf node
or not.
OK, so if leaf node, so basically the left and right, they both will be null.
OK, so if left is null.
And basically, right is also null.
OK, so not the error rate.
Is also tunnel, then this is basically Leelanau, so if this is not what I can do, so I can read and
adapt.
OK, so this one I can do that because that will be my answer.
OK.
So what I am doing here is I am checking for Liefeld, so my target was to find if not and if I find
out the lymph node, I can return it, that otherwise I was turned up left and right exist.
OK.
So our standard approach is basically what I will do, so check left exist, then Bush left.
So if left exist, then what I have to do so.
So let us construct an item, OK?
So I have this item, let's name it basically a.
So what its value and so the value will be, so the note will be no right or left and the debate will
be so this debt plus one, OK?
So this depth plus one.
Simple and then what I will do you not push this item is a simple.
Now we will do the same thing for the right one, for the right separately.
OK.
So basically, the right exist, so if that exist, construct a new item, so the node will be right
and that is again that plus one and Geldart wish a simple.
So this is the complete code.
I think they should work fine.
OK.
So in order to submit first we will run our code and then we will submit.
OK.
OK, so this is an excited, convolutional, OK?
So Q I don't mind getting a read this line.
OK, so basically what we are getting so we are getting the compilation error because that it was integer,
so I have to return something.
OK, so I have to return something.
Now, let's return.
A garbage value, so let us return zero.
OK?
So although this line will never get executed, OK, this will never get executed, but this is due
to the completion purpose.
OK, so this is only due to completion purposes.
We have to return something.
Because they don't have the function is in.
So I have to return something.
Now, let us Amitabha, good.
OK, so our goal is working fine now let us take a small example and let us write a novel code.
What is happening?
OK, so let's take a very small example.
So three nine 20, the example given in the question, OK, 15 and seven.
So what I'm doing so construct a Q item, construct a Q of the data type Kuwata, so construct a Q item
and then push.
So basically if this is the Q.
So I am pushing three Gormogon, OK, I am pushing through Gormogon.
OK, now, while the queue is not empty, so the queue is not empty, get different element and pop.
OK, so Bob.
So basically, what is F so F is basically three Guaman.
Now, it is basically Edward not.
So this is not and this is after that, so basically the node is basically three and that is basically
one, OK, now left and right exist.
So for three, left exist and right exist.
So this condition is false.
Move ahead.
So if left exist, construct a new item and push the left and the a value plus one.
OK, so that value plus one.
So that will become to construct a new item.
So it will be basically first three years left.
OK, so three arrow left which is nine.
So I will push nine Khama two.
So push nine Komada inside the cube.
So I have nine.
Now getting check for the ride, so right is basically to write this basically 20, so I will push it.
So it is a is basically going Takamatsu.
So Bush during the Commodore.
20 comida, OK, grundy's the root value and two is basically the debt.
Now again, while the queue is not empty, queue is not empty.
Bob, different element.
So different element this time around is basically OK.
So this is friend.
So is basically nine to.
Now, the Norder value is basically F Naude, which is nine LDAP values, basically after that, which
is two again.
So this time Majak for nine left is not right.
So left.
Mesnil right is nil.
So basically this condition is true.
This condition is true.
But I will return.
I will return that.
What is the depth and baptista.
So I will return to.
I will return to.
And two is the correct answer for this binary twisty correct answer for discriminately.
OK, so I am returning to here.
You can see done that.
So basically, that's how the school is working and as discussed, their time complexities big often
and the space complexity is also big often.
OK.
So basically, this line will never get executed because we will always have a leaf out of a tree will
always exist, so this line will never get executed because as we know, the meaning of a tree, the
leaf node of the tree will exist.
OK, but this line is important for the completion purposes because they don't have the function is
basically integer.
So we have to return something, otherwise the completion will be delayed.
OK.
So if you have any doubt in this question, you can ask me.
OK, thank you.