Welcome back.
Let's now code the solutions which we discussed.
Now we will use the same binary search tree which we created or constructed earlier.
All right.
So that we can just write the breadth first and depth first functions.
And then we will call it for the same object the BST object over here.
All right.
So let's get started.
So we are just continuing just to quickly give you a context.
We have the class node over here.
And then we have the class binary search tree.
And over here we have written our previous functions insert and find and remove.
And we continue over here.
All right.
So we have this was a helper method.
Get min.
Now we continue over here.
Let's get started with the breadth first search.
So breadth first let's call it uh breadth first.
And, um, we don't need to pass anything to it.
Now, as we discussed in the, uh, video previously, the approach that we are going to have over here
is we'll have a queue, and then we'll also create an array, which finally we will return.
Now, before we get started, let's just check whether the the binary search tree at this point is empty
or not.
So if this dot root is equal to null.
That means that the binary search tree is empty, and in this case, we just have to return an empty
array.
So that's that.
Now, after this.
Now let's get started with implementing the breadth first search approach, which we discussed.
So let's have let's say a variable array and let this be an empty array.
So we will as we traverse the binary search tree we will push data into this array over here.
And finally we will return this array.
All right.
So again I'm just writing this over here.
At the end we will just return the array.
So that's the approach over here.
And we will also need an empty queue.
All right.
So over here I just mentioning it over here we are to save time.
We are just implementing the queue as an array.
But that's not the best approach.
All right.
So that's just to save time.
Now even in the interview you can say this to the interviewer and go ahead and implement the queue as
an array if the interviewer is okay.
Now to get the best performance, we have to implement the queue as a linked list.
Now we have discussed that in a separate video previously.
Now over here again I'm repeating to save time.
And because that's not the central thing that we are doing over here, the central thing which you're
doing over here is the breadth first traversal approach.
Right.
So because of that, I'm just implementing the queue as a array over here.
So let's write that.
Let let me call the queue as queue itself.
And we're implementing it as an array.
All right.
So we are done with this.
Now to start with what we will do is let's have a variable.
Let's call it node.
And let's initialize this to the root node.
All right.
Now what we will do is we will push this root node into the queue.
All right.
So let's write that queue dot push.
And I'm pushing the node to the queue.
And then we will have a while loop, and we will keep iterating as long as there is something in the
queue.
So if q dot length is greater than zero we keep iterating.
So if q dot length is greater than zero, that means something is there in the queue.
We could also write while q dot length because zero in JavaScript is falsy, right?
So when q dot length becomes zero, that will break out of it.
But I'm just writing it over here as while q dot length greater than zero.
So both approaches are correct.
Now what we will do is first we will take the last the first in again remember Q is a Fifo data structure
right.
So that's why we are using a queue over here.
So we need to take out what came in first right.
So that would be at the beginning of the array.
Now again I'm repeating we are implementing it as an array over here to save time.
But if you are taking something out from the beginning of the array, we know that that's an O of N
operation.
So that's why it's not advised to do it in that manner.
But again, because that's not the central thing over here.
It's fine to do it like this.
So we will take out the first element from the Q array.
So for this let's say node is equal to q dot shift.
And shift takes the first element from the queue, right?
So we have taken out the first element.
Now what we will do is we will push this into the array.
So array dot push.
Node, we will push it into the array, and then we will check if there is something on the left of
the node or on the right of the node, and if it's there, we will put those elements into the queue.
So let's do that.
So if node dot left that means if there is something in on the left of the node then we will push it
to the queue.
So q dot push.
No dot left.
All right.
Again.
After this, we will check if something is there on the right.
So if no dot right.
If it's there we'll just push it to the q.
So q dot push no dot.
Right.
All right.
And we are almost done.
So again, we will come to this part over here.
And then because we have pushed something to the queue, if there is something in the queue, it will
keep iterating.
Now once we are done and there is nothing more in the queue, we will come out.
And at this point we just need to return this array which we have created over here.
All right.
So that's the end of our breadth first traversal method over here.
Now we have already created we have written the code to create this binary search tree.
So again I have these insert calls over here.
So let's run that.
And after that we will just call the breadth first method which you have uh written over here.
And what is the expectation.
Let's just write the expectation also over here.
Now again I'm writing it as a comment.
So breadth first search.
The output should be over here.
We should get 20 right?
Then we should get 635.
So let's write that 20 comma six comma 35.
And then over here we should get three eight 2755.
Right.
So three eight 2755.
And after that we should get these elements.
That is one three.
25, 29 and 60.
That's the expectation.
So let's go ahead.
And after we do creating, after we create this binary search tree we will call BST dot pred first.
All right so BST dot.
Breakfast.
And this is the expectation which we have over here.
Now let's run our code and see whether it's working.
All right.
So we have run the code.
And we are inserting nodes to the array.
So that's why we have an array of 12 nodes over here.
Right.
So let's again uh just check it.
So this is the output that we are getting.
Now we have 20 which is correct.
Then we have the node with value 630 538 2750 513 2529 and 60, which is correct.
So yes, our breadth first search is working.
Again.
We will look at this code in the walkthrough section and analyze its complexity again.
All right.
Just to be very clear with what is happening over here.
Now let's go ahead and implement the depth first methods which we discussed in the previous video.
So let me make some placeholders over here.
Let's call it DFS.
And we have to write three functions.
The first one is in order.
All right.
And the second one is DFS preorder.
And the last one is DFS.
Post order.
All right.
Now let's go ahead.
Now we start with in order again.
We start with checking whether the, uh, binary search tree is empty.
If it's empty, we will just return an empty array.
So to take care of that edge case, let's write if this dot root.
Is equal to null, then we will just return an empty array.
All right.
Oops.
Okay, so if that is not the case, then we proceed further.
So what do we do.
We need to have an array which will be the output right.
Which is what we will return.
So let's say const array.
It's an empty array.
Finally we will return this array.
Now we will need to traverse the binary search tree and push elements to this array.
So that's what we are going to do.
Now let's start with the root node.
Let's say current is equal to this dot root.
And we will write a function, right?
Let's write a function which will traverse the array.
So let's call it Trav.
And for this function we will be passing the node.
In this case that's the node root node.
And then over here we will call the function which is Trav.
All right.
So we will call it with the current node which is the root node.
At this point this is how it's going to work.
Now over here is where the recursive calls will happen.
Right.
So we are writing this as a function so that we can recursively call this function.
We could also write it outside but it's convenient to write it over here.
Now what is it that we have to do.
Remember inorder traversal.
Let's just quickly revise what we have seen before.
Let's say I have I'm just making some space over here.
Now if I have a node.
Let's say that's two.
And on its left I have one, and on its right I have three, right?
So if this is the case, if we are traversing this tree in order, that means first we have to go to
the left node, then the current node and then the right node right.
So that's the importance right.
So that will be the only difference between these three functions that we are writing over here now
for depth first inorder traversal.
First we go to the left.
Then we push the current node to the array.
And then we go to the right.
So let's do that.
So let's check whether there is a left node for the current node.
So if node dot left that means if there is a left node then we have to recursively call the function
for that particular node.
So trave node dot left.
All right.
Now, after this, after we are done with the left, we push the value in the current node to the array.
So over here we do array dot push.
And then that's the node right.
So that's node over here.
And then we check for the right.
Right.
So we are done with the left.
We are done with pushing the value of the current node to the array.
Now we traverse the right side.
So if there is a node on the right.
So if node dot right.
What do we do?
We recursively call the trough function for that particular node.
So node dot right.
And that brings us to the end of our breadth depth first in order function.
All right.
So let's quickly write these other two also.
And then we will just test them together.
Now again I'm just going to take the same code over from here because it's going to be almost the same
thing pasting it over here.
And let me paste it over here as well.
Now for pre-order.
Remember the order to be followed is for preorder.
It's.
Current and then left.
And then.
Right.
And for post order, it's left, right and then current.
It's left, then right, then current.
Now again, just for remembering.
Notice that left and right are always together.
Right?
You have left and right over here and left and right over here in these two cases.
And when you have three you have to put current as the first.
Right.
So pre means before.
So you can just remember it in that manner.
So you put current first.
And when you have post you put current last.
All right.
So again that's the only difference that we are that we need to make over here.
So for pre order we have to shift this to the first part.
So first we push the current node value into the array.
And then we traverse the left side.
And then we traverse the right side.
So that's it.
Now for post order we have to traverse left first then right.
And after we are done with both of these then we will push the value of the current node into the array.
So that's the only difference between these three depth first search methods.
All right.
So we are done.
We have returned all the three functions over here.
Now let's go ahead and call the function.
So let's have.
Probably.
We'll just do it one by one.
Now we have our array.
We have our binary search tree over here.
Now let's see what we get.
So let's go ahead and run the code.
And again, I'm going to amend this because we are already done with the breadth first part, but we
are only going to check or test the depth first part over here.
All right.
So we have created this binary search tree.
Now let's call the depth first functions that we have written.
So BST dot.
DFS.
Let's start with in order.
All right.
So.
Again.
Yeah, it just says that it's there.
I should have put the brackets.
All right, let's put the brackets.
Now we get 12 nodes over here.
Now again remember when we do in-order traversal on a binary search tree we will get the nodes.
The values of the nodes will be in ascending order.
So it's very easy to check.
So let's just check whether this is in ascending order.
So we have 13368, 20, 25, 27, 29, 35, 55 and 60.
So yes, this is in ascending order.
So we have the uh the DFS inorder traversal is working again just to quickly revise what's happening
over here.
We go to the left first right.
So we start at 20.
We go to its left.
We go to the left of six and we come to three.
We go to its left which is three, and there's nothing in its left.
Right.
So this becomes current and we push one.
So that's how we get one.
And then we go to its right which again is nothing.
So we come back.
So the left of this is done.
So this is now current right.
So we push this three.
That's this three over here.
Then we go to its right which is this three over here.
And then uh so this part is over this and this is over which is the left of this right left of the node
with value six.
Then we push the current node which is six.
We go to its right which is eight, and so on and so forth.
So that's how the breadth the depth first search in order works.
Right.
So we are done with that.
Now let's go ahead and check.
Depth first search.
Pre order and post order.
So we have DFS uh BST which is the binary search tree dot depth.
First.
Uh let's do it.
Um pre order first.
Okay.
All right.
So when we do this we are getting 12 nodes.
Again remember preorder is that what's the order.
We have written the order over here.
We need to put current first.
Pre means current is first current left and right.
So that's pre order right.
So we are starting at the node.
So you can see that the first node is 20 itself because that's the current and current is pushed to
the array.
Then after that we move to the left right.
So we come to six.
We push it in.
So we have six over here right.
So that's pushed.
And then we go to its left which is three.
And three is pushed because that is the current node at this point.
And then we go to its left which is one, and we push one.
And there's nothing more to go to its left.
So again we try right.
There's nothing in the right.
So we come back to here.
So we have done with current and we are done with left.
And then we go with right.
So that's this three over here.
So at this point we are done with current and the left of six.
So we go to the right of six which gives us eight.
And it goes on like that.
So that is pre order DFS.
All right.
Now again let's go ahead and try uh DFS post order.
All right.
So over here post order means we have to do left then right.
And then we come to the current node and push its value to the array.
So that's post order DFS.
So let's check.
So we start at 20.
We first have to go left right.
So we go left again.
We go left again we go left.
We reach over here.
There's nothing more to go left right.
So over here um we are done with left.
And we try right.
There is nothing.
Right.
So then we put the we push the current value, which is one at this point.
And one comes over here.
All right.
So after this we are done with this.
Now we come over here we did left.
Then we go right.
So this three is pushed over here.
Right.
Then we are back.
So left and right are then done.
So then this three is pushed over here to the array.
So that's this three over here.
So we are done with this part.
So this is the left of six right.
So after that we have to do the right of six which is eight.
So that's why you have eight over here.
Then left and right of six is done.
And then we push the current value which is six.
So you get six over here.
And at this point the left of 20 is done.
Then we start with the right of 20 right.
So we come over here again.
We go to the left.
And that's how we push 25 to the array.
And it goes on like that.
So yes, our code is working.
We have successfully coded the breadth first search approach and the three methods for depth first search,
which is in-order pre-order and post order.
Now let's take a quick sample, uh, um, binary search tree and walk through the code.
Because again, remember in the interview you will have to walk through the code once you have written
it.
And we will quickly relook at the complexity analysis of these methods that we have written.