Algorithm

  

 

 

 

DFS(Depth First Search) : Binary Search

 

 

 

Redraw the tree with some detailed information on each node for clarity. Of course, you would not want to do this if the size of the tree gets larger, but try to put this image in your brain and try to remind in image when you are writing the code.

 

 

 

Get the root node.

 

Mark it as visited (v = 1)

 

Put it into stack

Get the item on the top of the stack  shown in previous step (this is 'A' in this case).

 

Get the node on the left branch of 'A'. (it is 'B' in this case)

 

If it is unvisited(v = 0), mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here.

 

Get the item on the top of the stack shown in previous step (this is 'B' in this case).

 

Get the node on the left branch of 'B'. (it is 'D' in this case)

 

If it is unvisited(v = 0), mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here.

Get the item on the top of the stack shown in previous step (this is 'D' in this case).

 

Get the node on the left branch of 'D', but there is nothing on the left.

 

Get the node on the right branch of 'D', but there is nothing on the left.

 

Since there is no 'unvisted branch' on this item (D), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'B'.

Get the item on the top of the stack  shown in previous step (this is 'B' in this case).

 

Get the node on the left branch of 'B'. (it is 'D' in this case). But 'D' is marked 'visited' (v= 1). So do nothing for 'D'.

 

Get the node on the right branch of 'B'(It is 'E' in this case)

 

It is unvisited(v = 0). so mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here.

Get the item on the top of the stack  shown in previous step (this is 'E' in this case).

 

Get the node on the left branch of 'E', but there is nothing on the left.

 

Get the node on the right branch of 'E', but there is nothing on the left.

 

Since there is no 'unvisted branch' on this item (E), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'B'.

Get the item on the top of the stack  shown in previous step (this is 'B' in this case).

 

Get the node on the left branch of 'B' (it is D) but D is already visited

 

Get the node on the left branch of 'B' (it is E) but D is already visited.

 

Since there is no 'unvisted branch' on this item (B), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'A'.

Get the item on the top of the stack  shown in previous step (this is 'A' in this case).

 

Get the node on the left branch of 'A'. (it is 'B' in this case). But 'B' is marked 'visited' (v= 1). So do nothing for 'D'.

 

Get the node on the right branch of 'A'(It is 'C' in this case)

 

It is unvisited(v = 0). so mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here

Get the item on the top of the stack shown in previous step (this is 'C' in this case).

 

Get the node on the left branch of 'C'. (it is 'F' in this case)

 

it is unvisited(v = 0), so mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here.

Get the item on the top of the stack  shown in previous step (this is 'F' in this case).

 

Get the node on the left branch of 'F', but there is nothing on the left.

 

Get the node on the right branch of 'F', but there is nothing on the left.

 

Since there is no 'unvisted branch' on this item (F), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'C'.

Get the item on the top of the stack  shown in previous step (this is 'C' in this case).

 

Get the node on the left branch of 'C'. (it is 'F' in this case). But 'F' is marked 'visited' (v= 1). So do nothing for 'D'.

 

Get the node on the right branch of 'C'(It is 'G' in this case)

 

It is unvisited(v = 0). so mark it as visited (set v = 1), print it and put it into stack.

 

The result is as shown here

Get the item on the top of the stack  shown in previous step (this is 'G' in this case).

 

Get the node on the left branch of 'G', but there is nothing on the left.

 

Get the node on the right branch of 'G', but there is nothing on the left.

 

Since there is no 'unvisted branch' on this item (G), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'C.

Get the item on the top of the stack  shown in previous step (this is 'C' in this case).

 

Get the node on the left branch of 'C' (it is F) but F is already visited

 

Get the node on the left branch of 'C' (it is G) but G is already visited.

 

Since there is no 'unvisted branch' on this item (C), remove it from the stack.

 

The result is as shown here.

 

Now the top item on the stack is 'A'.

Get the item on the top of the stack  shown in previous step (this is 'A' in this case).

 

Get the node on the left branch of 'A' (it is B) but B is already visited

 

Get the node on the left branch of 'A' (it is C) but C is already visited.

 

Since there is no 'unvisted branch' on this item (A), remove it from the stack.

 

The result is as shown here.

 

Now the Stack is Empty

Process stops here since the stack is empty.

 

 

 

Reference :

 

[1] Depth First Search Algorithm