Hi, everyone.
So in this video, we are going to discuss the preorder, Trevor Salvatore.
OK, so what exactly are the traversal?
So suppose you have a root node.
You have left Sabri.
And you have right subtree.
So preorder traversal CS, first you visit the data, then you go to left and then you go to right.
OK, so what is the.
So this is basically raw data.
OK, so first visit the date of the root node, then visit the left subtree and then visit the right
separately.
OK, so data are left.
Right.
OK, data live right now, let's see this example and let us try to find out the broader traversal for
distri.
OK, so first of all, I'm standing here, so first data.
So one will get printed first, then the left subtree and then the right SIPRI.
OK, so what is the output for everybody?
So first to.
Then they left debris, so for then the right subtree fife, and finally this right subtree three.
OK, so this is the period reversal for this by Nutri.
Now, let us perform the trial set for distri.
OK, so first data.
So one, then the left subtree, so left three does not exist, then the right subtree.
OK, now first two, then the left subtree, which is three.
And then the right subtree, which does not exist.
So it is.
OK, so this is the traversal for this tree.
OK, one, two, three.
Now, let us consider this example.
OK, so first her data.
So that means 25.
Then they left Sabri.
And after left subtree, we have to go for it right subtree, so fallers are pretty a15 so 15 then they
left subtree, so then.
Then they live separately, so for then the right subtree, 12, OK, so 12, 15, then for 12.
Then right subtree, so data left, right.
So it will be 22, 18, 24, then 50.
Then again, 35.
So basically, Rita left and right, so 31 and 44.
So data 70, left, right.
So 66 and 90.
OK, so period reversal is very simple.
First you visit the data, then you visit the left subtree and then you visit the right subtree.
OK, so there is data left, right.
So we have to follow this order for each and every node industry.
OK, we have to follow this order for each and every node of the tree.
OK, so this is the period reversal for this by Nutri.
Now, I hope you understood the question.
So it's called will be very, very simple, but you have to do so.
Suppose you have a function visit.
So what this function will take as input, it will take root as input.
So first of all, data.
So I will print data.
So route data.
Then would I have to do I have to visit the left February, so I will call the function visit and it
will visit the left subtree.
And then I will visit the right subtree.
OK, so I will call the function visit and I will give the right subtree.
OK, very, very simple.
This is data, this is left and this is right.
So data left.
Right.
OK, so since so this is basically a recursive function, OK, the code is very simple.
Now, let us write the code since you have understood the logic.
OK.
So this is the question I have to write the preorder, Trevor said, and the output for this mandatory.
My output is one, two, three, OK, so I have to return vector of integers, I have to Rodenbeck profanity.
Just so first, let us rate what is a simple what is a simple builder driver said, okay, so let's
name dysfunction preordering.
So it will simply take.
No reason, but it will simply take root as input, not a simple case.
So if Rudimental that mystery did not exist, so I can simply return.
OK, I can simply return without printing anything now.
We have to do I have to first print get data.
Left, right.
So data left, right, so this is data then left.
OK, so I will call the function preorder.
And I will pass left.
So after I left.
I have to visit the right subtree.
OK, so I have to follow this order for each and every detail left, right.
OK, so this is very simple code for people traversal, OK, first data, then left and then right.
Data left, right.
OK, now we will modified this code for our question.
OK, so here we do not have to print anything.
We have to return vector of integers.
So let's create.
Avedon said, OK, so let's call it let us call this transfer.
Now I will call the function preorder.
And I will give Root as input and obviously the answer and once I would answer it is ready, I can return
my answer.
OK, I've put a ton of integers, so I'm returning on set here.
Now let us modify this code.
So basically it will take a vector of integer says input and it will fill that vector.
OK, so instead of printing.
I will store the elements, OK?
I have to store instead of printing, so Sadaat pushback value of fruit.
OK, very simple and let us a bit this also so.
Commands and commands.
And one more thing, I have to pass this by reference.
OK, I have to pass it by reference so that the changes are permanent, OK?
Now, let's turn our code and then we will try to submit our code.
OK, now let's submit.
OK, so success.
So our goal is working fine.
OK.
Now let us discuss the time and the space complexity for the preorder reversal.
OK, so consider one example.
So I have one, two and let's say three.
And then let's say for so how the people travel survey work, so I will pass the road and I am passing
the answer.
OK, so initially my answer is somebody then answered or push back rude values or the system.
So I will push one.
Simple, then I'm calling on the left hand side, so left and side is basically nil.
OK, so what is happening here is this is the call stack, so one is calling on the left hand side,
left hand side is basically nil.
OK, so if the route is null, return.
So I will return to one.
OK, then I'm calling on the right hand side, OK, root, right, so I'm calling on the right hand
side.
So when will call to.
One is calling on two.
Then what I will do, so I will push to inside, so we will get inside and then two will call on its
left, so left does not exist for two, so two will call on.
And if the route is well, I will return.
So I will return back to to.
Then will call on the right hand side.
OK, so two will call on three.
Then I will push three.
Then three will call on left, which is for so trivial, calling for.
Then Ford will call in it, so Ford will get inside, then four will call on the left subtree, which
is Nele.
So it will read, I will return to Ford, then Ford will return two, three, three will return to total
return to total return, Duvan.
And finally, of course, tech will become empty.
And this is my answer.
One, two, three, four.
OK, you can see data then left and then right.
So one data left separate does not exist.
Then two data left separate does not exist.
Then three data and then basically four and the right subtree for three did not exist.
So this is how we will get our answer.
OK, and we have to store, OK, we have to pass by reference so that the changes are permanent.
OK, so that time complexity is basically big often because we have to go through each and every node.
OK, and again, the space complexities big off and in the worst case.
OK, so this is same as what in order driver said.
OK, same as traversal.
OK, thank you.