Hello all and welcome back.
So in this video let us now try to see different traversals which are present to us in our binary tree.
So let's get started.
Now talking about traversals, we have discussed the same in generic tree as well.
That traversal is a way I can go or rather print my binary tree.
I would say so what is the order?
Or how can I go to each and every node, traverse on each and every node?
Okay, great.
So let us take a binary tree.
Say something as straightforward as this one.
To understand the concept majorly.
Let's say this is a binary tree okay.
And let me name the element as well one, two, three and four.
So the very first one is something which we have seen and done already.
it is pre-order.
Okay.
So in pre-order, we are already aware that root says or the parent says that hey, first print me,
first traverse on me.
And then basically go to my children, right?
Something which we have also printed our binary tree on in the initial videos.
So in this case I will first come to parent and I will print its value.
Then I will go to its child print its value.
Then I will go print its value.
We will return.
And finally I will go here so that I can print the value.
Parent is asking that hey, first print me and then go to my child.
That is what is known as preorder traversal.
Okay, great.
So let me just write it a little bit more clearly.
First parent.
And then child.
So the order of my traversal, if we even try to print it, it's going to be something like one, two,
four and three.
Okay.
So parent asking first for itself and then for tree or then for its child.
Uh, let us help.
Uh, let us see the visualization as well everyone.
So visualization will make it a lot more clear, right.
So in this we are going to visualize the preorder.
Okay.
Great.
So let me click this button and see.
First one gets overall printed.
Then it's two.
Then it's four then three then eight then finally six.
So let me replay this so that you can see it.
Uh the speed is lowest only should be fine.
So pay attention everyone.
What exactly happens First one, then two, then four, three, eight, six.
Okay, so the order, if we just pay a little bit attention, the order is something like this.
First one says that hey first print me or traverse on me.
Then it's two.
C two.
Then it's four.
Four okay then three.
After three it's children eight and then finally six.
Okay, great.
So let us try to code this clear pretty quickly.
Everyone def preorder traversal.
We will be getting a root okay.
This is something we have done already.
If root not equal none we can, right?
Is not none as well.
We can just return as it is.
Print root dot data and.
Print.
Sorry.
Preorder.
Traversal.
Root.
Dot left.
Preorder traversal.
Root dot.
Right.
Also in this we are always calling left first and then right.
Okay.
So we have to maintain that order.
It is not that if I am saying that children should be called that call my child, then it should.
It can be right or left.
No, that is not the case.
Let me write that as well.
Always.
We call left first
and then right.
Okay.
Because the order matters in this binary tree.
Great.
So cool everyone, let us see the output once for this preorder traversal.
Route one.
Okay.
One minute.
So let us run this.
We are not able to see output.
Okay.
So route if it is none.
Okay.
If route is none then I can return.
Else I have to just keep on calling and do the recursive call.
And now we see the output 124536.
Okay.
Let us see the tree.
Where is it.
Yeah.
So
124536.
Right.
See that it is fine.
Let us copy this as well.
Here.
Preorder.
Order because this is something we are going to use in future as well.
Okay everyone.
So I hope each and every one of you are able to understand how exactly is this a preorder traversal?
First.
The very first is the parent, then its children, then child, then child.
It goes back, then its child and then child.
Okay, cool.
So each and every node says that hey, first print me and then go to my children.
That is what is happening.
Great.
Now let us see another kind of a traversal which is known as post order.
Again, something which we have done in our generic tree as well.
Here we say that hey first.
First my children okay.
And then me.
So each and every parent says that, hey, first the child, both the child and then me.
So it goes from child to parent.
So this is exactly how it will go.
We will.
Come on one one will say, no, no, don't print me.
Go to two.
We will go to two.
Two will be like, hey, don't print me.
Go to four.
Four will be like, don't print me.
Go to my children.
It doesn't have any child, so I will print it.
So the first one is going to be four.
Then we will come back.
And we will print two.
So we will print two.
Then before one we will come back here again.
But this time as well one will say that hey, first please print my children, then print me.
So I'm going to see three and then finally one.
Okay.
So one will come in the end this time because it is in a way prioritizing its children.
Okay, great.
So let us see this as well in visualization.
Everyone.
Let us stop and let us visualize post order.
Great.
So yeah, let us see.
We come to one okay.
But it is not printed.
I think it will get green when it gets printed or it gets reversed.
One is going to make the call to two.
It is not turned green in pre order.
It turned green, which means that we have traversed or accessed its data.
As of now we have not done the same.
Two again will make the call to four and the call to four is made.
All right everyone, so you can see the calls how they are getting made.
One calls to two, 2 to 4.
They are not green as of now okay.
Not green which implies.
Not traversed or basically printed.
Okay, great.
So let us now move forward.
For no children are there, so it will turn green.
See, this is the first one to turn green.
So in my answer very first is going to be for now let's see which is the next one to turn green every
one.
Next one turns two as green.
Okay.
But you will notice one more thing here which is one is still not green.
And it called on three because I am doing post order.
I am saying that hey, first do all my children and again left, then right.
It's not that you can do either of them.
It's left first and then right now three will call on this.
Let us move forward.
So three calls on eight eight turns green third.
Now let us see Then it calls on six.
See?
Up till now as well, three is not printed.
Then it calls on six.
So six, then three.
And then finally one is left.
Okay everyone.
So I hope this overall visualization is helping you a lot.
Please make sure that you understand the whole intuition.
That's why I'm putting so much effort in explaining you the visualization.
This visualization is very important in making sure that tomorrow you are also able to solve the questions
on any other platform or in any way or in an interview.
Plus, it will be a lot helpful if you will be able to explain to your interviewer with this mindset
with these overall visualization or examples, not just by definition many students, they just remember
the definition.
And that is not what I want any one of you to do.
Okay, great.
So yeah, if the goal is clear, then maybe we can run this again more quickly to see.
Let us replay first one, then it goes to two and then four.
Four gets printed, then two, then three, eight, six, then three, and then one.
Okay, great.
So let us try to code this as well everyone.
Def post order.
Traversal okay.
Route.
I can actually copy this whole and easily make a single change.
The change is just going to be this.
So what I'm saying and I've copied this code in front of you so that you know that it's good.
If you have written some code in logic, just try to see that.
What changes can you do in that?
For easier code at least I am saying that hey, if route is none, then return else.
First call on my left, then call on my right and then finally call on me.
Okay, great.
So let us see the postorder traversal of one.
245361.
Okay.
So let us see this here as well.
Uh one minute it is calling 245.
Three.
Six.
One.
Just a second.
Okay.
Two, four.
Ah!
We have made a mistake, I think.
One minute everyone.
So again, should copy code less than great.
So, yeah, if you're copying the code, please make sure that we are handling everything properly.
Now, let us run this and it is fine now.
Okay, great.
So now we can see that first, then second, then fourth.
So fourth will get printed first, then five Once both the children have been done, then two.
Okay, then we will go on three.
But three will not get printed unless its children are printed.
So six, three and one.
Okay, so this is the case everyone.
So learning anytime we are copying the code please make sure that everything is checked.
Great.
So let me copy and save this as well.
Post order okay cool.
So there is one more traversal which is there in my binary tree.
So let us learn about that as well.
The last one is known as in-order traversal in-order.
Traversal.
In-order traversal basically says that hey first print the left one okay?
First the left.
Then me.
So each and every parent is saying like this, that make me a part.
Okay, take me in of the order, then the right side.
Okay.
So it becomes something like right or left child which is your left subtree.
Then your becomes parent and then it goes to your right child.
So this time my parent is saying that hey, make me a part.
Okay.
So how is it the answer is going to be one, two, four, three.
So one will say that hey first call on my left.
Two will say that, hey, first call on my left.
So the answer is going to be four because no left is there.
Then we can print two this time before sending to three.
One will say that hey, now make me a part and print me as well.
So one and then three.
Okay everyone.
So this is the in-order traversal the third traversal in our binary tree.
This again is not possible in generic trees because we have many children there.
Right.
Great.
So let us see the same in visualization as well.
Visualize in order.
Okay.
So let us run this and see one.
As of now we have just seen it will ask us to go to two.
Two will ask us to go to four.
Now, since four has no child, four will say that.
Okay, print me.
Then we will print two as well.
So let us run till here.
Now in the last basically the preorder traversal.
My post order.
Sorry.
In the post ordered traversal it one was not getting printed and it was sending it directly to three
to first get it printed post right?
Once all my children are done, post that print me.
So always remember this with these words post, print me, post all my children's pre, print me pre
all my children and in order print me within my children's.
So this call was sent to three.
But this time one will be like no print me within.
Okay, so let us see that in action everyone.
This time one turns green.
See?
First one turns green.
Then we can move forward.
Three will turn green.
Three will again not get printed.
What will happen here?
One is there, three will say that.
Hey, first call on left.
So left.
No children are there.
It will get printed this time again three will not send this call here.
Three will first get printed itself and then send the call.
So eight, three, Six.
Three.
Six.
Find.
The last one is the sixth.
So you will see one thing.
Fourth is the leftmost node.
Six is the rightmost node.
Right, everyone.
So I hope you are able to see this particular thing.
This is very important.
We will be doing some question going forward on this particular understanding.
So that's why I'm making sure that each and every one of you are able to understand it properly.
Okay.
So I will just write and summarize it down.
First let me write the code for in-order traversal as well.
That will be helpful.
So for in order traversal what we have to do we will be getting the root.
If root is none we cannot do anything.
We can just return okay.
Now first my overall root is like that.
Hey first call on my left.
Then you can print me if the inorder traversal of left is done.
So when I call this particular function at 24, this basically means in recursion terms that you have
done the preorder inorder traversal of left.
Okay, then print me.
This is the work which we are doing root dot data.
And once I am done, then just do the inorder traversal on my right as well.
And yeah this is how we should be fine that inorder traversal is going to work.
Again I will repeat first the left, then me, then the right.
Let us run this everyone and we see 425136.
Let us see it quickly so we will go all the way till here.
We will print four then two will print itself and then five will get printed.
First the left left subtree is done.
Once the left subtree is done, we will print one and then three and six, three and six.
Right everyone.
So I hope yeah, we are getting the same answer.
Let us copy and save this as well in order traversal.
Great.
So yeah I think these are the major traversal we already we also learned about the level wise traversal.
But that is majorly to make sure that we are able to see the tree more nicely.
Okay.
But majorly in questions you will be seeing these traversal being asked.
Okay everyone.
So let me summarize this once.
First we had.
Preorder.
Preorder says that hey, first print me, then my left child.
Like then do the preorder traversal on my left child and then do the same on my right child.
So this is how your preorder happens everyone.
This wall will be done.
Preorder.
This wall will be doing preorder.
Great.
Second is post order.
This time my route or the parent says that hey, first do it on my left child.
Then do it on my right child.
Then just route.
Okay, so again, this is the whole Function or traversal, which we are doing everyone.
And last is in order.
In which we say, first do the left child.
Then you can print me.
And then the right child.
Okay.
Yeah.
So something like this we have to do.
Let me make it nicely.
Yeah.
So this is exactly all the different traversals we have studied now in order was not possible in binary
genetic tree because we have multiple children.
Where are we going to insert our root node or the parent node.
Right.
But in binary tree it is very well defined which is your in-order traversal.
Okay everyone.
So I hope this is clear.
Properly these traversals are very important.
We will be using them to do some questions in the next videos, and they are also asked in many use
cases.
It can happen that any of these traversal is helping you to get to your answer or solve your problem.
Okay, so please make sure that you revise them properly and try to code it once without seeing the
code which I have written.
So now you have seen the understanding before the next video.
Try to code it once at your end.
Take a tree.
Maybe you can work on route two.
Write the code.
Write down the answer which you believe should be there and then check the same with your code.
Okay everyone, you will also have my code so you can just make sure that you are running it.
If in case you feel that your code is giving the wrong answer, okay.
But please make sure that this understanding gets clear within yourself a lot more nicely, so that
moving forward you can use them with a lot of confidence.
Okay, cool.
Then everyone, thanks a lot.