Hi everyone.
Let's do this question right.
For instance, methods for a binary search tree class to traverse the binary search tree method one.
Traverse the tree breadth first and return an array that contains all the values of the binary search
tree method to traverse the tree depth first in order, and return an array that contains all the values
of the BST method three traverse the tree depth.
First preorder and return an array that contains all the values of the BST, and finally traverse the
tree depth, first post order and return an array.
So this is the question.
Now this is a standard question.
So let's dive in and let's first discuss what's breadth first search and what is depth.
First search and notice over here we have three types of depth first search.
So let's get started.
First we understand what's the expectation.
And then let's discuss how we can solve this question.
So over here I have a sample binary search tree.
You can see everything to the right of 20 is greater than 20.
Everything to the left of 20 is less than 20.
So that's the binary search tree property.
Now when we traverse this breadth first.
So BFS is breadth first search right.
So what we do is we go level by level.
So this is level zero right.
So we go first this level then we go in this level right.
So 20.
Then we take 1340.
So we go to the next level 1013 and 43.
And the next level is 811 and 41.
So the output array should be this.
When we do breadth first search.
Right.
So when we traverse the binary search tree with the breadth first approach we should be getting this
output 2013 4010 1343 right.
So this is the next level then 811 and 41.
All right.
So we have understood BFS.
Now let's go ahead and understand DFS depth.
First search or let's traverse the binary search tree depth first.
Now as we have seen in the question there are three possibilities right.
We can do this in three ways.
We can do in order DFS, preorder DFS and post order DFS.
Now let's try to understand what these mean.
Let's get started with inorder DFS.
Now when you do inorder DFS right, what you have to think of is first we process the left side of the
particular node.
Then we process the current node right.
And then we process the right side of the current node.
So this is the order.
Now let's take a small example to understand what we mean with this.
So over here I have a binary search tree and it just has three nodes ten nine and 11.
All right.
Now left node.
We start with this one okay.
This is the root.
Now the left of this node is nine right.
So when if we traverse this tree in order dfs the output array will look like this.
First we go left which is nine.
Then we process the current node which is ten.
And then we get the right node which is 11.
So the array would look like this 910 and 11.
So this is inorder traversal of DFS type.
All right.
Now let's see how we can do DFS traversal on this binary search tree over here which is the sample one
which we have taken.
We start at the root which is 20.
All right.
Now first we go left right.
So we come to 13.
Right now when we come to 13 1313 is the current node.
So again we go left right.
And when we come to ten that's the current node.
Again we go left which is eight.
Now when we try to go left there is nothing more right.
So there is nothing more over here.
So we come back.
So eight is the current node at this time.
So we push eight to the array.
And then we check if there is anything on the right.
So again there is nothing on the right.
So we come back.
So from there we come back to ten.
Now we have completed the left side of ten.
Then we do the current.
So at this point ten is current.
So we push it to the array.
Then we check the right of ten.
All right.
So we go this way.
So over here we have 11 and we push it in.
So what's actually happening is we come to 11.
We check if it has anything in the left it does not have.
So it comes back.
So this is the current node.
We push it to the array.
Right.
And then we check whether it has anything in the right.
And it has nothing.
So it comes back and we come back to ten.
So at this point we have completed the left side of 13.
Right.
So this is the left side of this node over here.
This 13.
So that is done.
So left is done.
After that we process current right.
So when we come back to ten then we go from 10 to 13.
So 13 is current at this point.
And we push it into the array.
So the left of this node is done and the current node has been processed.
Then we go to the right which is this 13 over here.
And there is nothing in the left.
So it comes back.
This is current.
At that point we push it to the array.
We check its right.
There is nothing over here.
It comes back.
So this is done.
Now we go back to 13.
And at this point the left of 20 is processed right.
So this is the left of this node over here which is processed.
Now we come back to 2020 is current right.
So that's pushed to the array.
And then we check its right.
So we go to the right.
So which is 40.
When we go to the right 40 we check whether it has anything in its left.
It does not have anything in its left, so it comes back.
So 40 is current at this point.
We process current right.
And we push 40 to the array and then we check its right.
So we go to the right direction.
So we come to 43.
Now when we come to 43 this is current at at that moment right.
So then again we check its left.
So we go to the left which is 41.
And then this does not have anything in its left.
So we push 41 to the array.
It does not have anything in its right.
So we come back to 43 at this point.
Right.
So we come back to 43.
And at this point its left is done.
So 43 is current.
So that's pushed to the array.
And then we come back to 40 and it's already it's done right.
We are we are completed.
We have already.
That was the right side of 40.
Right.
So the left side of 40 was done.
Current 40 was already pushed.
And this is the right of 40 that is also completed.
And that brings us to the end of in order DFS.
So this is the output that we will get when we do inorder traversal of a binary search tree.
Right.
And notice over here when we do DFS in order, the array which you are getting over here is actually
in the ascending order.
So you have eight, ten, 11, 13, 13, 20, 40, 41, 43, which is the ascending order.
Remember when we discussed removal in, uh, the binary search tree, when we wanted to remove a node,
we discussed that we can replace that node with with its inorder predecessor or successor.
Let me just clear this.
All right.
Now let's quickly revise that.
Let's say you want to delete this node over here which is 20.
Now you can replace this over here with the value of its in-order predecessor or successor.
So over here we have 20.
Now you can see that its successor is 40 and its predecessor is 13.
Right.
So this is this 14 over here.
So remember how we got this.
We moved to the right.
And then we go as much to the left from here as we can.
But because we don't have anything over here we stay over here itself.
So this is its predecessor, its successor.
Right.
Inorder successor.
Now what about the predecessor?
So we go to the left and then we go right as much as we can.
So this will be the inorder predecessor.
So which is this one over here.
So that's what we discussed over there.
All right.
So I just brought this up as a side point.
So notice that when you do inorder DFS for a BST or a binary search tree you get the elements in ascending
order.
All right so we have discussed this.
Let's now proceed.
Now I've just placed this over here.
This is the BFS order the breadth first search.
And this is the in order.
So let me just write that this is in order DFS.
All right.
Now let's proceed and look at these two preorder DFS and post order DFS.
Now it's pretty similar to inorder DFS.
We just have to change the order in which we do these three operations over here.
So for the case of preorder we do the current operation first.
Then we move to the left and then we move to the right.
Now in the case of post order we do the left first then the right, and then we process the current
node.
So notice over here that you have left and right together in both these cases right you have left and
right together.
Now in the case of preorder you put current first.
Now pre denotes before right.
So you can just remember it in that way.
So when you have pre order you put current first.
And when you have post order post means last right or after.
So you put current last and then left and right are together.
So that's just a trick to remember this.
All right.
Now let's have our small binary search tree over here.
So it just has three nodes.
Now we have seen that when we do in-order traversal on this binary search tree we will get left which
is nine, then current which is ten and then right which is 11.
And we have seen that this is in ascending order.
Now in the case of pre order traversal, first we go to the current.
So we start at the root.
So this is the current.
So we push ten over here right.
And then we go to the left which is nine.
And then we go to the right which is 11.
So we will get ten nine and 11.
In the case of pre order DFS.
And in the case of post order DFS first we go to the left which is 11 right or sorry nine.
First we go to the left which is nine.
And then we go to the right which is 11.
And then we process the current node which is ten.
So we get 911 and ten.
So this is the post order DFS um traversal.
So let's now go ahead and see pre order and post order DFS traversal for this binary search tree over
here.
All right.
So let's just make some space.
Now let's start with pre order.
So we start at the root node.
And you can see that in the case of pre order first itself we do the operation on the current node.
Or we push this value to the array.
So we push 20 to the array.
All right.
So this is the output array.
Let's build it parallelly.
Then what we do we move left right.
So we move to 13.
Now 13 is the current node right.
So again we process the current node first.
So we push 13 to the array.
And then again we move left.
So now ten is the current node.
So again we push the current node to the array.
So let's do that.
So we put ten over here and we move again left because after current we do left right.
So again we are now at eight.
Eight is the.
Current node.
At this point, we push it to the array and we try to move left, but there is nothing in its left right.
And again we try to move right.
There is nothing in its right.
So we come back.
So at this point 410 we have processed the current node.
This is the current node and we have done the left.
So we go to the right right.
So the right over here is 11.
So we go to left.
And 11 is the current node at this point.
And we push it to the array.
And we try left and right which is not there for it.
And we come back.
So at this point this is the left of 13.
Right.
So the left of 13.
And this is current right.
So current is done and left is done.
So we go to the right.
So this is the right.
So we push that to the array and then we come back.
So at this point this is the left of 20 right.
The node 20.
So the left is done.
And over here we already did the current.
So current is also done.
Now we move to the right.
So we move to the right which is 40.
Now 40 is the current node right.
So we push the current node to the array.
So we have 40 over here.
Now we try to move left.
It does not have anything in the left.
So we try to move to the right.
So we go to 43.
Now 43 is the current node.
So we process the current node.
We push 43 to the array right.
Then we go left which is this part over here.
So we go left which is 41.
And that is the current node.
We push to the array.
We try to go left.
We try to go right and it does not have anything.
So at this point this is the left of 43.
Right.
So current is done.
Left is done.
And we try right.
And it does not have any right.
So this is the right of 40.
Right.
So left of 40 is empty.
We have already processed 40.
And we are done with the right of 40.
So this is also done.
This is the right of 20.
So we have done 20 which is the current node.
We have done its left and its right is also done.
So we stop right.
So all the call stack functions are done.
They have returned and we get our array over here which is 2013, ten, eight, 11, 13, 40, 43 and
41.
So this is the DFS preorder traversal of this binary search tree.
All right.
So let's just keep this aside.
And finally let's look at the post order DFS traversal of this binary search tree.
So again we start at the root node which is 20.
Now what we do is we first move left right.
So you will see that 20 will be inserted at the very end in this array.
So we move to the left which is 13.
Again we move to the left again we move to the left and we reach eight right.
And we try to move to move left.
And there is nothing in its left.
So we come back to eight.
We try to go to its right again.
Its right is also null.
So we come back.
So at this point eight is the current node.
So we tried the left of this node and the right of this node which is empty.
And then eight is now current.
So we process this node.
So we push eight to the array.
Now we are done with the left of this node right.
This is the left of node ten.
Now the left is done.
So we come back to ten and we move to its right.
Right.
So we have the right node over here.
Again 11 is the node.
We try its left and right which is null right.
So we come back.
So this is the current node and we push 11.
So at this point the left and right of node ten is done.
So we come back.
And now we process the current node which is ten.
So we push ten over here.
So at this point this much is done right.
This is the left of 13.
So left is done.
So now we move to the right of this node which is this 13 over here.
And again it does not have any left or right.
So we push this over here and we come back.
So at this point the left of this 13 and the right of this 13 is done.
So we process the current node which is this one over here.
So we process this and we insert 13 to the array.
So at this point this is the left of 20 right.
So the left of 20 is done.
So now we come back to 20 and process its right.
Right.
So after left we go to the right.
So we come to 40.
Now again from 40 we try left.
It does not have anything in its left.
So what do we do.
We go to its right.
So we come to 43.
Now from 43 again we try left which is 41.
So we come to 41 and then it does not have any left.
It does not have any.
Right.
So it comes back.
This is the current node at that point.
And we push it to the array.
So at this point we are done with the left of 43.
Right now we come back to 43 and try for its right.
Now we see it does not have a right.
So again we come back and we process the current node which is 43.
So 43 will be inserted to the array.
So at this point the left of 40 is done which was empty and the right of 40 is completed.
So 40 becomes the current node.
And we process the current node which is 40.
So that also gets entered inserted into our array.
So at this point this is the.
Left of the right of 20.
Right.
So we finished the left of 20.
And just now we finished the right of 20.
So we come back and we process the node 20 and we insert 20 to our array.
And this is the postorder traversal.
So this is the array that we get as output when we traverse this binary search tree with DFS Postorder.
All right.
So we have understood BFS and DFS and the three types of DFS which is in-order pre-order and Post-order.
Now let's go ahead and try to see how we will code this solution.
All right.
So let's discuss the method and the complexity analysis.
Now first let's start with breadth first search or BFS.
So again we have our binary search tree over here.
And we have already seen that the output expected.
Is this right 20.
Then we need 13 and 40.
Then 1013 and 43 and then 811 and 41.
So we go level by level.
All right.
So this is the expected output.
Now let's see how we can code this.
So for this we will use a queue.
All right.
So let's have this queue.
And this is an empty queue over here.
And we will also have an array.
So the array will be the output array which is this one over here.
And we will build it.
Now we will start at the root node and we will push what is there in the root node into our queue.
So let's do that.
So we push 20 to our queue the value of the root node 20 to our queue.
All right.
Now we will have a while loop.
And we will keep iterating or we'll keep repeating going through the loop as long as there is something
in the queue.
All right.
So just let's walk through this code and you will understand how this is working.
So we will have a while loop over here.
Now inside this once we're inside this.
So we are sure that there is something in the queue right.
Because that's the condition while something is there in the queue.
So once we are inside it we will take what is there in the queue.
And that means we will take the first element right.
So we will dequeue from the queue the first element.
Because remember a queue is a Fifo data structure right.
First in first out.
So this is the leftmost element in this array.
Over here will be what was entered first right.
So we will take that out and we will push it to the array.
So we will have 20 pushed into the array.
So let me just write it over here we have dequeue and push inside this while loop.
And after this we are now at node 20 right.
We will look whether it has a left child or a right child.
And if it has a left child, we will enqueue that value to the queue.
And if it has a right child, we will put that value to the queue.
So let's do that over here n queue left right.
So over here the left child is 13.
So we put that value into the queue and then we enqueue the right child.
So over here we have 40.
Again the value of the right child 40 is put into the queue.
So we have 13 and 40.
And that's the end of the while loop.
Now again we check whether there is something in the queue.
Yes there are two elements.
Right now you can see 13 and 40.
Are this layer like this level which is level one.
So we can see there are two elements over here 13 and 40.
So yes there is something over here.
So again what do we do.
We dequeue from the queue which is 13.
Right.
So we dequeue from the queue which is 13 and we push it to the array.
So we have 13 put into the array.
Now the node where we are at is 13.
Right now we check whether it has a left or a right child.
And if it has we push those values to the queue.
So in this case enqueue left will put ten inside right.
And enqueue right will put the value 13 inside our queue.
And that's it.
So again our queue is not empty right.
So what do we do.
We take the first value from the queue and we put it to the array.
So we dequeue and we push to the array.
And then now we are at this node 40.
And we put the values of its children to the queue.
So in this case there is no left child but there is a right child.
So 43 gets put into the queue.
All right.
So again the queue is not empty.
So at this point what the next value that we take out is ten.
So we take out ten and we push it to the array.
And now we are at node ten right.
And its children eight and 11 are added to the queue.
All right.
So again after that the queue is still not empty.
Now we go to 13 right 13.
So we again dequeue 13 and we push it to the array.
Now 13 over here does not have any children so nothing gets added to the queue.
Next we dequeue 43 and we push it to the array.
And then 43 has the child 41.
So that value gets added to the queue.
Next again we take out eight eight does not have any children.
Similarly 11 does not have any children and 41 does not have any children.
So eight, 11 and 41 respectively get added to the array.
And that gives us this output over here 2013 4010, 13, 43, eight, 11 and 41.
So this is how we do the breadth first search.
So notice the method over here we use the queue.
And then we start from the root.
Now we take that value out from the queue put it to the array right.
So that will be the first element in our output array.
And then its children get added to the queue.
Right.
So 13 and 40 were added over here after that.
We take out 13, and then ten and 13 were added.
So you can see that we are slowly, uh, going from level by level and we are going left to right,
and we are adding those values over here and it's children get added later.
Right.
So this is how we tackle the breadth first search so that we get the output and the arrays.
The array contains values level by level.
All right.
Now let's go ahead and discuss the complexity analysis of this solution.
Now the time complexity for this solution will be o of N, right?
Because we are just visiting every node once and doing some constant time operation on it by dequeuing
and then pushing it to the array.
Right.
So we are just visiting every node once and doing some constant operations.
So the time complexity is clearly O of n.
Now what about the space complexity?
The space complexity over here is O of n because we are making an array.
Right.
And the size of the array will be of length n because there are n elements.
Now if this was not the case, if we just had to visit and print it, for example, and we were not
storing those values in an array, for example, in that case the space complexity will be O of W,
where w is the maximum width of the binary search tree, right.
So this will be the approximate maximum size of the queue at any time.
So we are just making this queue over here.
Right.
So this queues maximum size approximately will be of the order of the width of the binary search tree.
Now over here when we build the queue you can see that at some point we had maximum of four elements.
Right.
So that is the width.
Width at this case is three.
This is the maximum width three plus one.
So it's w plus one in this case.
But this is just a constant.
So we can avoid that.
So the space complexity will be o of w where w is the width of the queue the maximum width of the queue.
In this case it's three.
Now let's look at the worst case and the best case in terms of space complexity.
And we are taking the case where we are not building an array.
Right.
So we are taking this case where we probably just have to traverse the binary search tree and print
those values.
So we are not creating an array.
So in this case the space complexity is O of w.
Now let's look at the worst and best case of O of w.
All right.
Now for the worst case.
If the tree is a balanced tree, right?
If the tree is balanced, then it will have the maximum width right?
So in that case there will be log n levels which is the height, and the last level will have two to
the power height nodes.
Right.
So that will be two to the power log n and two to the power log n is nothing but n right.
So in this case the space complexity will be o of n.
Now again how is it.
How did we get that.
We found that w in this case will be two to the power of height.
Right.
And in the case of a balanced tree and height is log n.
So two to the power log n is n.
So in this case in the worst case w can be n.
So the worst case complexity over here will be o of n.
Now again two of log n is equal to n.
Let me just quickly show that to you.
If you have not remembered that, no problem.
Let's quickly discuss that log eight for example is equal to three.
And we know that that's so because two to the power three two to the power three is equal to eight.
All right.
Now instead of this three which I have over here, let me just replace it with log eight so I can say
two to the power log eight.
Right.
So this three I am replacing it with log eight.
So two to the power log eight is equal to eight right.
So you can see two to the power log n is equal to n.
So that is what we have applied over here.
That's how we got that.
The worst case.
In the worst case the width of the tree will be n.
And in that case the space complexity will be o of n.
All right.
And what about the best case.
The best case will be O of one if the tree is skewed right.
If if there is just one node per level and you have a binary search tree that looks like a linked list,
for example, something like this one, two, three, etc. and then for something like this, right.
So over here that's a skewed binary search tree.
Now if that is the case then the maximum width is just one right.
So the best case space complexity will be O of one.
In the case of a skewed tree, all right.
So we have discussed the breadth first search.
We have discussed how we will implement it.
And we have seen that the time complexity of BFS is O of n and the space complexity is O of n.
Because over here we were creating an array of size n, right.
But if that was not the case, the space complexity would be O of W.
All right.
Now let's go ahead and discuss the the complexity analysis of the three DFS approaches which we discussed,
which is in-order pre-order and post order.
And again, before we go to the complexity analysis, let's discuss how we will implement this in code.
So we will have a function let's call it Traf.
And then this function will take in a node.
All right.
So once we reach a node then what is it that we do.
Let's just first discuss in-order traversal.
And then the other two are just pretty much similar.
All right.
So once we reach a node over here you can see we have to go to the left node first.
Then we process the current node.
And then we go to the right node.
So this is what we will do over here.
So we have this function Trav.
And again we are passing in a node.
So we are at a particular node.
Then we will check if there is a left node.
So if there is a left node then we will recursively call the same function trav.
And we will pass that particular left node.
All right.
Now once it comes back we will process the current node.
And processing the current node means pushing the value of the current node to the array.
So that's processing the current node.
Right.
So over here we will say array dot push.
And we will push the value of the current node.
And again this is just pseudo code right.
So I'm just writing over here.
But it should be the value of the current node.
And then finally after we have we are done with processing the current node.
We will just go and look at the right node.
Or we will traverse the right side right.
So that we will be done by again recursively calling the draw function.
And over here we will pass the right node.
So that's it.
So this will give us the in-order traversal the in-order traversal of this binary search tree.
Let's quickly see what's happening over here.
We start at 20.
All right.
So we are let's say we are inside this function.
Does it have a left node.
Yes.
So we go over here again.
Now this is we are again in the next call of traverse.
Right.
So this is 13 at this point.
Does it have a left uh node.
Yes it has.
So at this point again we move left.
Again we go for a new call of the function.
Right.
So again we go left at this point.
And at this point there is nothing in the left right.
So we come we it returns back and then we are at this.
This is the current node.
And then we push eight to the array.
So that's how we discuss that.
In the case of in-order traversal we will first get eight over here right.
So eight is done.
And that's the current node at this point.
And this now we will try its right.
And again there's nothing.
So we will return.
So at this point the left of ten is done.
Now we will push ten which is the current node.
And then we will go to its right.
Right.
So that's pushing happens over here.
And going to its right happens over here.
So we go to 11 and then we again call the function.
You try to go left.
But we can't because there's nothing.
Then we push the value, which is 11.
We try to go right, we can't, so we return.
So at this point the left of 13 is done right.
So then we push 13 which is the current node.
So this is the current.
So we push 13 and then we move to its right which is this 13 over here.
So again and that's how we build the array over here which we have already discussed.
So this is the way that we will code the DFS inorder traversal.
All right.
So let's just make some space.
And I keep this aside now.
Let's discuss pre order and post order.
When you notice this over here you can see that this difference between these is just miniute right.
It's just the difference between the order.
So that's the only difference that you will see when you code this.
So let's discuss pre order.
In the case of pre order we will push or do the operation on the current node first which is this.
Over here we will push the value of the current node to the array.
Then we go left and then we go right.
So you can see we have just changed the order right.
We have just made this first.
And then we have this and then we have this.
So this gives us pre order.
Now in the case of post order this will be last.
That's the only difference.
So we have array dot push last.
First we go left.
Then we go right.
And then we do the operation on the current node.
That is we push the value of the current node to the array.
So that is how we will implement DFS in order pre order and post order.
All right.
Now let's quickly look at the complexity analysis of this solution.
Now it will be the same for all these three right.
We are just changing the order over here.
Now the time complexity will be equal to O of N because we have to visit every node once and do some
constant time operation on that node.
Right.
Like for example, you have to push that value to the array.
So the time complexity will be O of n.
You can say O of constant into n, and this is just a constant.
So we can remove it and we get o of n as the time complexity.
Now what about the space complexity?
The space complexity over here will be O of N because we are building an array, right?
We are building an array of size n two return.
Now if this was not the case, if we did not want to do that, and let's say we are just traversing
and printing the values, we are not creating a new array.
In that case, the space complexity will be O of D, where d is the maximum depth.
Right?
Because we will be using multiple calls on the call stack.
So we'll use some memory from the call stack.
So that will depend on the depth of the tree right.
Or the height of the tree.
So the space complexity over here will be O of d.