Binary Tree DFS Traversal

West Hollywood, LA

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

Algorithm

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.

Inorder

Preorder

Postorder

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  https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

// 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 */
        s.push(curr);
        curr = curr.left;
    }

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

    System.out.print(curr.data + " ");

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

}