Hi everyone.
Let's do this question.
Write a function that takes the root of a binary tree and returns the level order traversal of its nodes
values that is, from left to right, level by level.
So this is the first part.
Then let's continue reading the question.
And then we will come back and try to think about what it means with level order traversal.
So let's read initially write an instance method for the binary search tree class to insert the values
given as an array into the binary tree from left to right, level by level.
Each value in the array which is not null is to be made a node and added to the tree.
See examples below.
Then write the function mentioned first, which is this one over here.
All right.
So first let's think about the insert function.
Now we will be given an array of values.
So for example if this is the array which is given to us we have to take each value.
So we take the first value.
We make it a node and then we make it the root of the binary tree.
Then we take the next value and we add it over here which is the left of the root.
Then we take the next value we added over here, which is the right of the root right.
And then we keep doing this we take the next value we added over here which is the left of this node.
And we take this value.
We make it a node and we add it over here which is the right of this node.
So this is the insert function.
Now we may also be given values null.
So what do we do in that case.
Let's look at this example.
Over here we have the array 123 null and four and five.
So we take again one and it's made the root.
And two and three are added to its left and right right these nodes.
And then we have null over here.
So the left of two will be null.
And then the right of two will be four, and then we have five, which is the left of three.
So this is how this works.
All right.
So this is the insert function which is mentioned over here.
And this is to be an instance method for the binary search tree class.
So this is something that we have to write.
And then now let's look at the level order traversal.
So we have to write a function for the level order traversal of the binary tree.
All right.
So that is what is mentioned over here.
Now what is it when it what does it what does it mean with level order traversal.
For example for the case of this binary tree over here, we have to return an output array where each
level is put into one array.
For example, over here the first level just has one element and the second level has two and three.
So that's why we have an array with the values two and three over here.
And then the third level has four and five.
So we have an array with four and five over here.
Now what about this binary tree over here.
If you do a level order traversal of this binary tree the output would be one.
Because in this level we just have one.
Then we have two and three which is the second level.
So we have two and three one an array with two and three over here.
And then we have an array with four and five which is this level over here.
All right.
So we have understood the question.
We have to write a function for level order traversal of the given binary tree.
And before we write that function we have to write an insert function.
And we will be given an array of values.
And they have to be created.
Nodes have to be created with those values and inserted into our binary tree.
All right.
So that's the question.
Now let's go ahead and think about a few test cases.
Now the insert function is pretty straightforward.
So we have that over here.
Now let's think about a few test cases about the level order traversal.
Let's say the binary tree which is given to us is this one over here.
Now what would be the output.
The output would be 711 comma one and 539.
Right.
Seven is one level.
Then we have 11 and one which is one level.
And then over here in this level we have five, three and nine.
So that's 539 over here.
Now what if the binary tree is just having a root node right.
For example this is the case.
It just has one node which is the root node.
In this case the output array will just have one element.
And that would be an array with just the element seven.
And if the binary tree is empty then we will just return an empty array.
Now again remember you can come up with the test cases along with your interviewer.
So it will be good if you ask the interviewer whether it's okay that you come together up with the test
cases, because that will ensure that you are on the same page and you have understood the question
properly.
For example, you can ask, what should I do if the, uh, the, uh, the binary tree which is given
to me is just a null tree.
So then probably the interviewer says, in that case you can just return an empty array.
So this is something that you have to agree with the interviewer.
All right.
So we have understood the question.
And we have also looked at some test cases.
In the next video.
Let's first discuss the method or how we can write the insert function.
And after that we will take a look at the level order traversal function.