Depth first search code snippet

Question

I have this code for breadth first search:

var queue = new Queue<BinaryNode>();
queue.Enqueue(rootNode);

while(queue.Any())
{
  var currentNode = queue.Dequeue();
  if(currentNode.data == searchedData)
  {
    break;
  }

  if(currentNode.Left != null)
    queue.Enqueue(currentNode.Left);

  if(currentNode.Right != null)
    queue.Enqueue(currentNode.Right);
}

Now I am trying to do the same for depth first search and I know that DFS uses stack instead of queue so could I get some help on writing the DFS.

Answer 1

The simple answer is.. Just change the queue to a stack! (assuming it's a binary tree)

If you want to traverse from left to right you should invert the order of the pushes (like I did):

stack.push(rootNode);

while(stack.Any()) {
  var currentNode = stack.pop();
  if(currentNode.data == searchedData)
    break;

  if(currentNode.Right != null)
    stack.push(currentNode.Right);

  if(currentNode.Left != null)
    stack.push(currentNode.Left);

}

So.. This will traverse the tree:

in the order:

A -> B -> D -> E -> C -> F -> G

The order of operations will be:

1. push(a)
2. pop ; a
3. push(c)
4. push(b)
5. pop ; b
6. push(e)
7. push(d)
8. pop ; d
9. pop ; e
10. pop ; c
11. push(g)
12. push(f)
13. pop f
14. pop g

Another way

There's a similar way using recursion (it will be like using an implicit stack)

def dfsSearch(node, searchedData):
    # Base case 1: end of the tree
    if node == None: return None  

    # Base case 2: data found
    if node.data == searchedData: return node 

    # Recursive step1: Traverse left child
    left = dfsSearch(node.left, searchedData)
    if left != None: return left

    # Recursive step2: Traverse right child
    right = dfsSearch(node.right, searchedData)
    if right != None: return right

    return None