Binary Tree DFS Traversal

West Hollywood, LA

I recently revisited the DFS tree traversal and decided to summarize what I relearnt


Algorithmically, DFS (on a Binary Tree) can be expressed as a simple recursive function -

  • traverse(node)
    • traverse(node.left)
    • process(node)
    • traverse(node.right)
The order of the steps within the function changes depending on the flavor of the DFS used - 
  • In order
  • Pre order
  • Post order

Depth First

The name of the algorithm is a little confusing, however here are my main takeaways -
  • DFS does not stipulate that we start with the deepest leaf node. 
  • We process nodes with a bias towards processing the deeper nodes
  • The general direction is from left of the tree towards the right of the tree.




A non recursive method

The recursive solution is easy to understand and remember, however in an alternative solution it is also possible to utilize a stack to keep track of nodes that need to be processed.

The general idea -

  • Traverse all the left nodes whilst saving the nodes in a stack
  • When you reach the end (null), process the top of the stack.
    • This should be the left most node in the traversal
  • Now repeat this process with the right node of the just processed node

Here is part of the source for an in order traversal from

// traverse the tree
while (curr != null || s.size() > 0)

    /* Reach the left most Node of the
    curr Node */
    while (curr !=  null)
        /* place pointer to a tree node on
           the stack before traversing
          the node's left subtree */
        curr = curr.left;

    /* Current must be NULL at this point */
    curr = s.pop();

    System.out.print( + " ");

    /* we have visited the node and its
       left subtree.  Now, it's right
       subtree's turn */
    curr = curr.right;