In last post I talked about Breadth First Search. An alternative to that, is Depth First Search, used in cases we want to check upto a depth level first rather than breadth.

So let’s look back at the last example

This time we would like to parse something like

1. Check Root- 10

2. Check till depth level for one node- 18,7

3. Repeat for other nodes 22,15 and then 5, 12

A straight forward way is to modify the Breadth First Search algorithm to use Stack instead of Queue.

1. Push Root Node R to Stack S
2. Pop s node from S
3 a . If s.val is required value, return Success
3 b. Else Push all Neighbor/ child nodes to stack
4. If Stack is not empty, Repeat from 2
5. If Stack is empty, we have traversed all the nodes and not found the required node. Return failure.