Welcome back.
So we have successfully returned the four instance methods for breadth first traversal and depth first
traversal.
All right.
Now let's take some sample input and walk through the code.
And this is an important step in interviews as well.
So when you do coding interviews you will be asked to do this.
All right.
So let's get started with the breadth first traversal approach.
So we are inside this function.
We check whether the binary search tree is empty.
If it's empty we just return an empty array.
Now if not we go ahead and we initialize an array and a queue.
Now remember over here we are implementing the queue as an array.
But that's not the best way.
So we are just doing that over here to save time.
And because that's not the uh, central center part of the question which we are dealing over here,
right over here, we are dealing with breadth first traversal.
Now to get the best performance in terms of time complexity, we have to implement the queue as a linked
list.
All right.
Now we have a variable node.
And this is pointing to the root at this point.
All right.
Now we push this node to the uh queue.
So we have a queue.
So let's let this be the queue.
Now it depends on the question.
You can either push the node or you can push the value.
It depends on the question.
So over here we are pushing the node.
So we have the node 76 in our queue.
And then we have this while loop right.
So now the length of the queue is greater than zero.
So we are inside the while loop.
And then we say node is equal to q dot shift.
So we are taking the first element out right.
So we are taking this out.
And again remember we are we we are taking this out from the beginning of the array.
So that's why we ideally should be implementing this with a linked list.
Because that will give us an O of one time complexity if this was a linked list.
All right.
So this is the this is an array at this point.
Right.
So again just mention that to your interviewer that you're doing this as an array to save time.
Now we take out this 76 and we push it to the array.
So we have an array.
Let me just call it a over here.
And we push this to the array.
Now again you can either push the node or the value depends on the question.
Now over here you have 76.
Then you enqueue or you push into the queue right.
It's left and right children.
So over here this is the node.
It's left is 50.
So we put 50 over here.
And this has been taken out already right.
We put it over here.
Now we push to the queue 50 and then 80.
All right.
Now again we come back over here and we see that the queue is not empty.
So we take 50 and we put it into the array.
So that's happening over here.
We take 50 and then we put it, we push it into the array.
Then we are over here.
And then its child 43 is there.
So we put that into the queue.
We have 43 over here.
Now again we come over here we see that the queue is not empty.
So we take 80.
We take it out from the queue using the dot shift operation over here.
And we push it to the array and we are at 80 and its children 78 and 90.
Right.
These two are pushed into the queue over here.
So we have 78 and 90.
Let me just write it like this over here.
And then again we come over here, we see that the queue is not empty.
We take 43, push it to the array and and 43 does not have any children.
Again we come over here.
The queue is not empty.
We take 78, push it to the array and it does not have any children.
Again we come over here and we take 90 and we push it to the uh array.
And it does not have any children.
So at this point the queue is empty.
So q dot length is not greater than zero.
So we come out of it and we return this array.
So this is the breadth first traversal approach.
So we have 76.
That's this over here.
Then we have 50 and 8050 and 80 and then 4378 and 90.
So this is how we implement BFS.
Let's now look at the DFS in order traversal.
All right with the same binary search tree.
So let's say we have called this function.
Now we are inside this.
Now over here we are checking whether the binary search tree is empty.
And we see it's not empty.
So we come over here and we have an array.
I'm just writing it as a we initialize it and it's an empty array at this point.
And then we have a variable current.
So current is pointing to the root node at this point.
Now at this point we have this function again it's not called.
And over here we call the function.
So let me just write the call stack over here.
And I will just write it so that we can keep track of it.
Because this is a recursive solution.
So we are calling the function.
And the node which is passed over here is the current node which is 76 at this point.
Right.
So let me just write this like this over here.
1276 now over here, we are inside this function right now we are checking if it has a left node.
So node dot left at this point is truthy.
So we call again the function with this node 50 over here.
So let me add that to our call stack.
So again we have traf with the node 50 at this point.
Now we are again inside the function graph.
And the node is 50 right.
So over here.
So from 76 we came to 50.
Now again inside this we are checking whether node dot left is truthy.
Yes node dot left is truthy because you have 43 over here.
So again we call traf with 43.
So let me.
Write that over here we call the trap function with 43 at this point.
Now again we are inside this function over here.
Right.
So let me just clear this up.
All right.
So we are again over here.
Now we are checking if node dot left is truthy.
But this is null right.
This is null.
It's it does not have any children right.
So this is null and null.
So this is not truthy.
Right.
So it does not go over here.
Then we come over here and we do array dot push node.
So the current node is 43.
So we push this to the array.
So I'm just writing 43.
Over here you can either push the node or the value depending on the question.
So we are writing 43 over here.
Now we come to the next line of the code.
We are checking whether node dot right is truthy.
But it's not right.
There is no child over here.
So this is falsy.
So this does not execute.
And we come out of this function right.
So this call over here is removed from the call stack.
And we are back with with this call right at 50.
So when we had traversed 50 again let me just clear this up.
So at this point when we are calling the function with 50, we are done with this line.
Right.
So we went left and we came back.
Now we do array dot push node.
So this 50 over here is pushed into the array.
And then we we say we check whether node dot right is truthy.
In this case this is null right.
So this is not truthy.
So this also does not get executed.
And we come we come out of the function.
So this call is also done right.
So now we are in the trough call where we did the call with 76 as the node.
Right.
So we are done with the left part over here.
So this is done.
Now we come over here right because we just returned this.
So that's why this is done.
Now the current node is 76 and we push this to the array.
So let me write 76 over here.
And then we go to the right.
So we check if node dot right is truthy.
Yes it's truthy.
So we come over here and we come over here.
And we again add to the call stack.
Right.
So we have traversed now with 80.
So we call this with 80.
Now at this point again what we come inside the function.
Let me just clear this up.
We come inside this function again.
We check if no dot left is truthy.
Yes it's truthy.
So again over here let me just write it over here.
We add Prof with 78.
Right.
So we come again inside the function.
And this does not have anything in the left right.
So over here it this line does not get executed when we call the function with 78.
So we come to the next line which is array dot push node.
So this 78 gets added to the array.
Then we check whether node dot right is truthy.
No.
In the case of 78 it does not have anything in the right as well.
Right.
So it returns.
So this is removed from the call stack.
So 78 is removed.
And at this point when we did the call for 80 we have completed the left right.
So this is done.
Now we do array dot push node with 80.
So we add 80 over here.
So this line is done.
Now we check for the right.
So we go to the right and we see that yes this is also truthy.
So again I'm just writing it in a small manner over here.
So we are calling try with 90 over here in the call stack.
Right.
So again we come over here inside this function.
Now we check for left of 90 which is false.
So this does not get executed.
Then we do array dot push node.
So this node is pushed.
We have 90 over here.
Then we check for the right.
So again that's false.
So this also does not get executed.
And we come out of this call.
So this is done at 90 is done.
So again we are at the call for 80 right.
So for 80 what all is done.
We have completed the left part.
We have completed pushing the node and we have completed the right part.
So we come out of this.
So we come out of the 80 also.
And this is also removed from the call stack.
All right.
Now just the call which is remaining is the 76 call right.
The call on trap function with 76.
So for 76 we have done the left part.
And we also did the array dot push where we were at the current node which was 76.
And now we have just now finished the right part as well.
So this is the right part right.
So that is also done.
So this also returns.
And our call stack is empty at this point.
And we have our output array which is 43 then 50.
Then you have 76 then 7880 and 90.
And notice that the DFS in-order traversal for a binary search tree gives you the array in ascending
order.
And that's what we have over here.
The time complexity of this solution is O of N, which is the same case as the breadth first search
as well, because we're just visiting every node once and doing some constant operation.
But in terms of space complexity, you can see that the space complexity is O of D, where d is the
maximum depth of the binary search tree, right.
In this case.
So this can go up to O of n in the case of the worst case where you have a binary search tree that looks
like a linked list.
All right.
Now over here this is O of log n because this is a balanced binary search tree.
And the depth is O of the depth is log n.
Right.
All right.
So we have seen the DFS in-order traversal.
Now let's look at the others which is preorder and postorder quickly.
So it's the same case right.
So we have just changed the order over here.
So nothing else.
So the time complexity space complexity is the same.
And over here what's happening.
Let's just look at preorder first we start at 76.
We push it to the array right.
And then we go left.
So we go left.
And over here yes it's there.
So at this point we call the uh tree function with 50.
So initially it's called with 76.
So let me just track that.
And now we called it for 50.
All right.
Now, when we come for 50 again we push 50.
So array dot push.
So we push the 50 into our array.
And then we again call it on its left which is 43.
So we have 43 at this point.
Again at this point we are over here.
We push it to our array.
We have 43.
And so at this point we come check its left and its right and there's nothing over there.
Right.
So we are done for this call and this returns.
So this returns.
So now we have the call for 50.
So for the call where we call the drive function for the node 50, we are done with this line where
we pushed 50 and we are done with the left.
Now we check for the right and nothing is there in the right.
So this is also done.
And this returns right.
So now we are in the call where we call the function for 76.
Now in this case the array dot push is done and its left is done.
Now we call its right.
So we again call the try function for 80.
So I'm just writing to 80 over here.
And at this point we push 80 to the array.
Because in this line array dot push node we push the 80 right.
And then we check its left.
So yes it's there.
So we again call T for 78.
And we push it at this line.
We push it right array dot push.
Then we check its left and right which is which is not there.
It's null.
So this returns.
And then we come again to the call for 80.
So for the call of 80 we are done with pushing 80 and we are done with its left.
So now at this part we call its right.
So we go over here again we call try for 90.
And at this point we push 90.
We check its left and right which is not there.
So this returns and this is taken out from the call stack.
And now 80 is also done right.
So 8080 was pushed its left.
We took care of its left and its right.
So at this point this returns right.
So we come back to 76.
Now in this case 76 we already pushed it and its left was taken care.
And its right is also now taken care.
And this is the output that we are getting 76.
Then we get 50, 43, 80, 78 and 90.
So this is the pre order traversal where we go where we push the current first then we go left then
we go right now.
Similarly we you can just check the post order.
Also it will be very much similar.
So you can just try it out on your own.
You can write the call stack like this and try it out on your own.
Now remember the time complexity for these are also O of N, because we are just visiting every node
once and doing some constant time operation, and the space complexity is O of D, where d is the maximum
depth of the binary search tree.