Welcome back.
Let's now go ahead and write the insert function which we just now discussed.
So over here we have our node class.
So we will use this to create each node.
And then we have our binary tree class over here.
And over here is our insert function.
Now an array will be passed to it which has values in it.
We will take each value and we will make a node out of it.
And we will insert it to the binary tree.
So this is what we are trying to do over here.
Now let's get started with this function.
And again over here you can see I have created three is equal to new binary tree.
And then we have called the insert function.
And we have passed this array over here.
And again we wanted to insert more values.
So over here we have again called the same function.
And we have passed this array over here.
All right.
So let's go ahead and complete this function over here.
First we are going to check if the array does not have any value in it.
So if array dot length.
If that is equal to zero, then we can just return.
All right.
Now, if this is not the case, we're going to check if the root is null.
For example, over here you can see we have called the function for the first time right.
The insert value.
And there is no value or no node in the binary tree at this point.
So when we call this this function over here, we'll have to take the first value and make it a node.
And we have to make that particular node the root node.
So that is what we are checking over here.
Now let me have a variable I.
So let's say let I is equal to zero.
Now we will use I to traverse the array which is given to us.
All right.
Now let's go ahead and check if the root is null.
So for this we are just going to say if not this dot root.
Right.
So that means the root is null.
So no node is there over here.
So we are going to take the first value from the array and make it the root.
So before we do that we also have to check whether this value over here which is passed is null or not.
Right.
Because we have seen in the example that sometimes null value also can be passed.
So that is okay if it's not over here.
But if the first value itself is null and the tree does not have a root, then we will just return.
All right.
So let's just check that.
So if array at zero.
Is equal to null.
If this is the case, then also we will just return.
Now, if this is not the case, then we will go ahead and create a new node.
So let's say let node is equal to new node.
And we will pass the value at the zeroth index.
So array at I or zero.
Again we know that it's zero.
So I'm just writing it over here as zero.
And then we will say this dot root.
Is equal to this node which we just now created.
And after we're done with this, we will increment I, because we have already used up the, uh, the
value at the zeroth index right in the array, which is passed to us.
Now, at this point, we're just going to check if I is equal to the length of the array.
If that is the case, then we are done right?
So if the array which was passed just had one element in it.
Now when initially I is zero.
But when we increment this over here I will become equal to one.
So I would be equal to array dot length.
If the array had only one element right.
The array which which passed to us.
If this had just one over here.
So that that's the case that we're discussing.
In this case we can just return.
So we can say return this.
That means we are returning the, uh, the current, uh, binary tree.
Right.
So when we call it.
All right.
So that's it.
So we have we are done with creating this part where we took the first element and we make it the root.
If the root is not there.
And then we are just going to continue.
Now we are out of this function.
Now let's just continue.
And again, as we've seen, we are just going to insert the remaining elements and we will be using
a queue for this.
All right.
Now initially the queue will just have the root.
So let's just say const queue.
Is equal to.
And again we are using an array because this is JavaScript and there is no inbuilt queue data structure
in JavaScript.
And for this to work in optimal time complexity, we would have to use a linked list to create the queue.
But then to save time and because that is not the central part in this question, we're just going to
use an array over here.
Now you can mention this to your interviewer if he or she is asking you to write this.
So you can say that you're using an array over here just to save time.
And most probably they'll be okay with it.
So over here we say const queue and then we have the root already inserted to the queue.
So we say this dot root over here.
Now we are going to have a while loop.
And as long as something is there in the queue we will just keep looping.
So while queue dot length.
All right.
So this is um again similar to breadth first search, what we've discussed.
So this is the same thing that we are using over here.
Now let's take the first element from the queue.
So let current is equal to.
Q dot shift.
So we're taking the first element from the queue.
So again the queue Q is a Fifo data structure.
First in first out.
Right now we're going to check for the left side of the current node whether it's empty or not.
So let's just check that if current dot if not current dot left right.
That means there is nothing to the left of the current node.
If that is the case, and if the value at the ith index is not null.
So let's just check that.
If not if array at I.
Let's say if array at I.
Not equal to null.
So if this is not equal to null, then we will just create a node with that value.
And then we will insert it at current dot left.
So let's say let node is equal to new node.
And then we pass the value.
So array at I right.
So we create a node.
And then we are going to say current dot left.
Is equal to node.
And once we're done with this we have used up the element at the ith index.
So we have to increment I.
So we say I plus plus.
And then again we're just going to check if I is equal to array dot length.
If that is the case then we just inserted the last element in the given array.
So we can just uh return the binary tree.
Right.
So return this and we come out of this.
All right.
So once we are done with this we also have to enqueue the element right at the left.
So let's again say if current dot left.
And we're just going to NQ.
So over here we'll just say Q dot push.
And we will push current dot left to the q.
Right.
So this is the same thing that we discussed in the video.
So we are doing we are pushing it to the queue because again later at the later point we want to see
if we have to insert more elements.
We have to see the left and right of this particular node, which we now just now enqueued.
So that is why we are putting it back to our queue and we are done with this part.
Now let's proceed and do the same thing for the right.
So this was for the left.
All right.
So that this started over here and we pushed it to the queue.
So we are done.
Now we are doing the same thing for the right.
All right.
So let me just write a comment over here.
And then it's the same thing.
We are just checking whether the current is there.
So if if there is there something at current dot.
Right.
So let's say if not current dot right.
So if nothing is there and the value at the ith index should not be null.
So again we are checking if array.
At I if this is not equal to null.
So if this is the case then we will create a node.
So again let node is equal to new node.
And the value that we are passing is array at I.
And we will say current dot right?
Is equal to this particular node.
Now, once we're done with this, we have used up the value at the ith index.
So we have to do I plus plus.
And again we will check whether I is equal to array dot length.
So if that is the case then the value that we just made a node and inserted was the last value in the
array.
So in that case we can just return the binary tree and we can exit the function.
So if I is equal to array dot length.
In this case, we will just return the binary tree.
All right.
Now, once we are done with this, we also have to enqueue the current element.
So again.
We say if current dot right.
Then we will NQ it.
So we say q dot push.
And we pass in current dot, right?
All right.
So that is it.
So that brings us to the end of the function.
So once we are out of this while loop we are done.
So we'll have inserted all the values.
Now let's go ahead and run the function and test our code.
So over here we have some values.
Let's try running this code.
All right.
And let's take a look at the binary tree that we get.
So we have the node.
So let's just take a look over here.
We have inserted the values 12345 and then 678.
So we have the node with value one which is correct.
And then on its left and right we should get two and three right.
So let's just draw this out for for us to visualize it.
Let me just draw this out over here.
And then we will just try to compare it with the output that we got.
All right.
So this is the out this is the graph or sorry this is the binary tree that we have just now created.
Now let's take a look.
So we have one over here which is correct.
Now let's open this up.
Now we have two and three.
Two is to the left and three is to the right, which is correct.
Now let's go down this path.
So four and five are over here which is correct.
And then for four we have eight and null which is also correct.
This is correct.
And let me just open it up for five.
So for five it should be just null and null which is also correct.
So we have checked this part.
Now what about this part.
Let's just open up three.
So for three the children are six and seven.
Yes that's correct.
And for six it's null and null.
And for seven also it should be null and null.
So yes our code is working.
Now let's also try to run the same thing for the, um, the array which we discussed in the concept
video.
And let's try to create that same binary tree.
So I have this over here.
Let me just remove this and let's just run it.
All right.
So let me just clear this up.
And we will also try to create the binary tree for this input.
So let's do that together.
So let's do that over here.
Now initially it's seven so we have seven at the root.
And then it's 11 and one over here.
So 11 and one.
And then we have null.
So 11 has a child which is null.
And then we have seven over here.
So we get again seven over here and two and eight.
So we have two and eight over here.
And we have null and null.
So these two are the children of seven.
So these two are null.
And then we have null and three.
So for two there is the left child is null.
The right child is three.
And then we have null and null for this.
This is for eight, right.
This is null and null.
And then we have five and null.
So that is for three right.
Because all of these are already null.
So we don't need to again write null for these cases.
So over here we have five and null.
So it's for this node over here which which will have the children five.
And then this is null.
All right.
So this is how our tree looks like.
Now let me just remove the nulls so that it doesn't get confusing.
Right.
So let's just remove the nulls.
So this is how our tree looks like.
Now just let's run the code and see how it is.
So let's let's see whether we are getting this binary tree using our code.
So let's go ahead and run it and let's take a look at the output.
So we have the node over here which is the root node.
We have seven.
That's correct.
And on its left we have 11.
And on its right we have one.
That's correct.
Now let's check for 11.
The children of 11 the left node is null and the right node is seven which is correct.
And for seven the children are null and null.
So that is also correct.
Now what about for one.
Let's open this up.
For one we can see the left child is two and the right child is eight.
So that's correct.
Now for two the left child is null and the right child is three.
That's correct.
And for three the left child is five.
The right child is null.
And let's just open up five.
Also over here it should be null and null.
So this part also is correct.
All right.
So let's now check for eight.
For eight it should be just null and null.
All right.
So yes our code is working.
Now let's now proceed and see how we can go about the second part of the question.