Depth First Search on a Binary Tree

Question

I have the following implementation of a Depth First Search algorithm:

 public static void printDFS(Node root) {
        Stack<Node> stack = new Stack<Node>();

        stack.push(root);
        while(!stack.isEmpty()) {
            Node curr = stack.pop();
            System.out.println(curr.getValue())      ;
            if (curr.getLeft() != null) {
                stack.push(curr.getLeft());
            }
            if (curr.getRight() != null) {
                stack.push(curr.getRight());
            }
        }
    }

and when I run it on a tree that looks like this:

                        0
                      /   \
                     6     7
                    / \   / \
                   5   4 3   2

I get the visited output as: 0 -> 7 -> 2 -> 3 -> 6 -> 4 -> 5

Is this a 'correct' DFS ordering? I would have expected the output to have been a pre-order traversal (ie 0 ->6 -> 5 -> 4 -> 7 -> 3 -> 2) and I know I can get this by first pushing the right node of each subtree. But what I want to know is what is the correct visitation order in a DFS algorithm?

Answer 1

As already mentioned in another answer the reason why your visitation -> traversal order is "inversed" lies in the fact that you are using a Stack to keep track of the "current node".

Let me walk you through your example tree:

                    0 
                  /   \
                 6     7
                / \   / \
               5   4 3   2

stack.push(root) leads to following stack state:

0: 0 <-- (root) and Top of stack

You're popping the stack and put it in curr. In traversal terms you are now in this state:

                    0 <--
                  /   \
                 6     7
                / \   / \
               5   4 3   2

you then proceed to add curr.getLeft() to the stack and then curr.getRight(). This leads to following stack state:

1: 7 <--(curr.getRight()) <-- Top of stack
0: 6 <--(curr.getLeft())

Repeating the same step we get following traversal state:

                    0 
                  /   \
                 6     7<--
                / \   / \
               5   4 3   2

and after adding the nodes:

2: 2 <-- Top of stack
1: 3
0: 6 <-- (initial getLeft())

as both nodes have no children, popping them from the stack and outputting them gets us to following traversal state:

                    0 
                  /   \
              -->6     7
                / \   / \
               5   4 3   2

The rest of this is history ;)

As you specificially asked about a "correct" way (or ordering) for a DFS: There is none. You define what side you traverse to depth first.

Answer 2

It's a stack. What you push last will pop first

Answer 3

There is no such "correct DFS ordering". The main idea of DFS is to go deep; visiting children before siblings for any given node. Once you go far deep in the graph and you encounter a leaf, you backtrack and examine the nearest sibling in the same way.

The way you choose which child to examine first result in different traversing orders (or trees). Needless to say, all traversing methods result in a spanning tree over the graph. Pre-order traversing, the one you are comparing with, is probably the most well known order for DFS (or at least this is what I have seen). Others are valid but not too popular.