Welcome back.
In this video, let's take a look at how we can write our insert function.
And as it is mentioned in the question we will be given an array.
Let's say this is the array which is given to us.
So we will have a variable, let's call it I, which will be used to traverse the array which is given
to us.
Now at this point our binary tree is empty.
Let's say it's empty.
All right.
And we also will need a queue.
And we start over here.
So we have to make this our root node right.
So we take the root and we will insert it to our queue.
Now because the binary tree at this point is empty.
We will take this node, the the value over here, we will make it to a node and we will make it the
root of our binary tree.
So we have seven over here which is our root node.
And in our queue we have our root node over here.
All right.
Now we have used up this element.
Now therefore we will just shift I to the next element.
Now if it was given if we were calling this insert function where the binary tree already has a node
at the root.
In that case we will just continue with I over here and the method will be the same.
All right.
So in that case we will just insert the root node to our queue.
And then we will proceed.
And I would not be shifted ahead.
But over here let's say the binary tree was initially empty.
So we have used up this value over here to create a node.
And that has been made the root node.
And the root node is added to our queue.
So this is where we are at.
And we have shifted I to the next element.
So I is pointing to 11 over here which is at index two which is at index one.
All right.
Now what we will do is we will do something very much similar to breadth first search.
So we will have a while loop.
And as long as something is there in the queue we will keep looping.
So if something is there in the queue we will dequeue.
That would be the first step similar to breadth first search.
So we take out this seven over here.
All right.
And now we are going to check if there is something to its left.
All right.
So if there is nothing on its left what we will do is we will take this value.
If it is not null right.
If it is null, we won't take it.
But over here we can see this is not null.
So if it is not null, if the value is not null, we will take it and we will make it to a node.
We will make this a node.
And then we will add it to the left over here.
All right.
So at the present moment nothing is there over here.
So we will we will add it to the left of the current node.
And then we will increment I.
We will increment I.
So I will point to the index two which is the next value over here which is one over here.
All right.
Now we have something over here in the left right.
So we need to enqueue it to our queue so that in the next pass right when we go to the next level,
we will check whether there is something to its left or to its right.
So that's why we need to keep enqueuing elements.
So at this point we are just going to enqueue what is there on the left of our current node.
So we put this 11 over here to our queue.
All right.
So we are going to enqueue this.
Now let's just write it into our queue.
Now if it was the case that the tree which is given to us already had a few nodes, for example, it
already had something over here.
In that case we would see that there is something on the left.
So this would not execute.
But this will still execute, right?
Because it's there, we will still put it to our queue because we want to in the next pass.
When we dequeue this we will check for the children positions of this particular node.
All right.
So we have done this for the left.
And I has shifted to index two over here.
Right.
This is index two.
This is zero one and two.
So I is at index two at this point.
Now whatever we did for left right these two steps we are going to repeat the same thing for the right
as well the right of this current node.
So we are going to check if there is something in the right.
And then we we will enqueue that particular node to our queue.
So so that is what we're going to do.
So at this point nothing is there on the right.
So what we will do is we will take the value and check whether it's null.
So we see it's not null.
So we will create a node out of it.
And then we will insert it at the right of the current node which is over here.
All right.
So let's do that.
And then we will just increment I.
So over here we will increment I.
So we get I to the next value in our array.
And then we will check if there is something in the right.
So because we just now inserted it will be there.
Now even if the tree was existing already and there was something at the right, we would have put it,
pushed it to our queue.
So at this point we pushed this to our enqueue to our queue.
All right.
So let's get one over here.
Now you can see this is similar to breadth first search right.
These steps this and this and Dequeuing this is there in our typical vanilla breadth first search which
we have discussed.
All right.
So let's just clear this space.
So we've got 11 and one over here.
And we our eye is now pointing to null.
All right.
So this part is over.
Now again we come over here and we see that we have these two elements in our queue.
So the queue is not empty.
So we come inside the while loop and we dequeue.
So we dequeue 11.
Now we are going to check its left and right.
So over here the value is null.
So when we come to its left though the left is empty right.
We don't.
It's null.
So the left of 11 is at this point level null.
So we don't have anything over here.
So we could have inserted at the left of this node.
But then the value over here is null.
So we just go ahead and increment I.
So we increment I and we move on.
Now we come over here and we check its right.
We see that its right is also null.
So we can create a node out of this value.
And we will insert it at the right of 11.
And then we will increment I.
So we increment I and we move over.
And then we are going to enqueue this element to our queue.
So we get seven to our queue.
Again we come over here, we see that we have these two elements in our queue right.
These two are there in our queue.
So we'd queue again and we have dequeue this node over here at this point.
And now we are going to check its left.
And right now there is nothing in its left.
And so we can make a node out of this value which is two.
And we insert it at its left.
And over here we are just going to increment I.
So we come over here.
Now we check its right.
So there is nothing in its right.
So we make a node out of this value and we put it over here.
And again before that we have to enqueue this two.
So we enqueue two over here.
Then we come over here we we make a node out of this value.
And we say that the right of the current node is this node over here.
And then we are going to enqueue this also.
Right.
So we get a eight also over here.
And then we push I ahead.
So I comes over here and we get eight also to our queue.
Again we come to the while loop.
We check this condition.
We see that the queue is not empty at this point.
So we dequeue, we take out seven and we are going to check its left and right.
We see that its left and right are empty, right.
So again we come over here, we see its left is empty.
So we have the value.
But the value over here is pointing to null right.
So we ignore and we proceed ahead and we increase the value of I.
Right.
So we come to the next element.
This also is null.
So when we check its right even though its right also is is null.
We could have inserted the value.
But because this is null we don't create a node and we proceed ahead right.
And we increment I.
So we increment I and we come over here again.
We come over here, we see that the queue is not empty.
So we take this element over here which is two.
And we are going to check its left and right.
Now its left is also empty.
But because this is pointing to a null we proceed ahead, right?
So we increment I and we proceed ahead.
And at this point we check its right and we see that its right is also pointing to null.
So we make a value a node out of this value.
And we insert it over here which is the right of this node.
All right.
And then we are going to enqueue this right at this step we're going to enqueue it out into our queue.
So we get three over here.
All right.
So we get three over here and we increment I.
So we have three in our queue.
And we incremented I to null.
Now we are again back.
We are checking our queue.
Our queue is not empty.
So we dequeue we dequeue this eight over here and we are checking its left and right over here.
And these two are empty.
But because it's null over here we're just going to proceed.
Right.
We will just increment I and we will just increment I again.
So this part is done and we come over here again.
We check our while loop.
The queue is not empty.
We have three at this point.
So we dequeue three and we are going to check its left and right.
Now its left and right are empty.
So over here we have five.
We will make a node out of this and we insert it at the left of this particular node.
And then we will increment I and we will push I to this five to our queue.
Again we come to the right of this.
And because the value over here is null.
So at this point we we are done with our array.
Right.
So we have completed our array and we don't insert anything over here because this value over here is
null.
Now we will when we increment I, we will see that I will be equal to the length of the array.
So we have nothing more to check for inserting.
So at this point we can come out of this loop.
So this is how we will go ahead and write this function.
Now in the next video let's try to code this out together.