Hi, everyone.
So in this video, we are going to discuss what is in seat.
OK, so suppose you have.
This is the root node, you have the left subtree and you have the right subtree.
So in order, Traversal says, first you visit the left subtree, then the data of the root node, so
D stands for the date of the root node and then visit the right subtree.
OK, so in traversal means first left subtree, then the current route node data and then visit the
right separate.
OK, so suppose this is an example of a binary.
So what will be the reversal of this.
So first of all, I have to follow this order left, then data and then the right subtree.
So for one, this entire part is left.
OK, then one will be visited and then the entire right path.
So one will be in the middle.
Now let's see.
So for two, this is the left subtree for so two will be in the middle and four in the left hand side
and five in the right hand side because 550 right separately.
OK, so four one three three right hand side.
So three will come here.
OK, so this will be the inner traversal for this tree.
OK, so you can see clearly for when one is the root node.
So this is the left subtree of one and this is the right subtree of one.
OK, so similarly two is the root node for this Sabry.
For this subtree two is the route also to welcome in the middle.
This is the left subtree for two and this is the right separate photo.
OK, so this is how travel still works.
Now let us perform in our travels along this big tree.
OK, so let's see.
So 25 but I have to perform.
I have to visit left first.
So go to left again.
Go to left again.
Go to left.
So for so first of all, four will come ok then it will go to its parent.
So its parent is ten so I will print ten then.
It's right subtree.
OK, well so this is basically left subtree then.
Data and right subtree.
OK, so for 10 12.
So for chromatin now for 15.
Left subtree has been visited.
So now 15 because they OK and left data.
Right.
So now come to 22.
So for 22 I will visit left subtree.
So it will come first, then 22 and then for 20 to visit the right subtree.
So 24.
OK, so for twenty five then entire life has been visited.
Now visit a. 25.
So right.
25.
Now, since the data has been visited, so I have to visit the right subtree.
OK, now let's visit the right.
OK, so 450 I have to visit the left subtree, left data.
Right.
So it will be 31, then 35.
And then 44.
So 450 has been visited now visit 50.
And now is it the right subtree, so it will be 66, then 70 and then 90, so 66, then 70 and then
90.
OK, so this is the traversal for this mandatory.
OK, symbol.
Now, let us discuss the proposal for this by.
OK, so for one, the left separate does not exist, so left is null.
OK.
Then visit their daughter after visiting the left to visit their data and now visit the right subtree.
OK, so forto I have to visit left first, so I will visit three, then I will visit data, which is
two, and then I will visit the right subtree, which is OK.
So one, three, two is the traversal for this binary.
OK, so I hope you understood the logic first I have to visit left pray for every node, then the data
of the current node and then the right subtree of this node.
OK.
So this left data, right, this is valid for every node.
OK, we have to follow this order for every node, not just for the root node.
We have to follow this order for each and every node in the banditry.
OK, so how are we going to solve this question?
So what will with the code?
So our logic is very simple.
First, I will visit the left.
So first I will visit the left subtree.
So suppose I have a function visit.
So visit function the left subtree, then I have to print the current data.
So which is.
Raw data, and then I have to visit the rights every so often visiting the right subtree, I will call
the function visit and I will give the right subtree.
OK, so we have to write these three lines.
So dysfunction will be a recursive function.
OK, so our goal is going to be recursive, then able to function as basically with it and it is taking
root, not as input.
OK, so we have to follow this order first, visit the laboratory, then visit the data and then visit
the right subtree.
They are.
OK, so since you have understood the logic, now let write the code, OK?
So basically, this question, bindery Binley, they are trying to settle this question, is president
unlettered?
OK, so now let us complete this function, OK?
So you can see here, if the if this is the Binetti, then our output is one to two.
OK, so basically I have two redundant broken pieces we don't have to print.
We have to store it and then we have to get it done.
OK.
So let us first write a simple Internet proposal.
OK, so let's call this function in order.
So suppose it so it takes root, núñez and put.
So first of all, what is the best case?
So basically, it is very simple if rotational.
Then you can simply done there's no need to do anything.
OK, now what do you have to do with the left February first?
So I will call the order function and I will say, hey, visit the left first.
Now, after visiting the left subtree where they will do so, I will visit the current route.
No data.
So.
OK, so rude Altobello.
And after visiting the data, I have to call on the right pretty early.
OK, now we have to call Andy right Subtree.
OK, so this is basically the simple code of ordinary traversal, OK?
Is very simple.
First, I am visiting the subtree, then the data.
And then the right subtree.
OK, simple.
OK, so now let us modified this code for our problem, so I have to return vector of integers, so
let us create a vector.
Veterans to restore our answer.
OK, now let's call this function in order.
OK, so I'm calling the function in order.
I will pass.
They do not.
OK, and I will also have to pass this vector.
OK, distractible, storable, resiled and finally I will return my answer.
OK, I have to return Retrophin pages, so I am returning my answer here.
OK, so let us modify this function.
So it is taking the root node and it is also taking a vector of individuals.
OK.
Let's name a dancer here also.
OK, now, instead of printing the value, what I will do so I will put the value inside the vector.
OK, so answer that.
Push back.
So I'm pushing the value instead of bringing the value.
OK, now one thing, I have to pass this by reference, OK?
I have to pass this vector by defense so that the change is that permanent.
OK, so that here when I'm returning the answer, it is containing the values.
OK, so I have to pass vector by reference, ok.
It is mandatory.
So this is the complete code.
Now letters are now a code and then we will submit.
OK, so there's some mistake.
OK, so we have updated our code, so I have to also pass answer here and similarly, I will pass answer
here.
OK, now let's meet.
OK, so success.
So our goal is working fine.
OK, now let's discuss the time and the space complexity.
OK, so basically, what is the time, complexity?
So what we are doing, we are going through each and every node, so the time complexity is basically
big off and and what is the space complexity?
So space complexity will be all that often OK.
This is due to the concept called stack.
OK, this is called Stack.
So what can happen to our Bindweed can be good to.
OK, so what is as good a tree?
So one, two, three and four.
OK, so this is the example of a school tree.
OK, so what will be the traversal for distri, it will be for three the.
OK, so dedication Kostic what will happen?
So basically, one one will call on two, two will call on three.
Three will call on four and then four will get printed.
Then three will get printed and two will get printed and then one will get printed.
OK, so here they are.
Four node's.
So there are total for in the military and stack sizes basically forward.
OK, so that's why if there are any notes in the worst case, the space complexity will be big often.
OK, in the worst case, space complexity will be big often.
So finally complex.
It is big often because I have to print each and every note.
I am going through each and every node and space complex.
It is big, often in the worst case when the given tree is basically as good a tree.
OK, not a balanced tree.
It is a school tree.
So I hope you understood this question.
OK, thank you.