CODEWITHSUNDEEP
algorithm
jcm
jcm

Reputation: 5659

Depth First Search on a Binary Tree

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?

Upvotes: 9

Views: 9637

Answers (5)

Jayant Arora
Jayant Arora

Reputation: 43

Here is a pseudo code for DFS:

''' This is much more of a traversal algorithm than search. '''

Algorithm DFS(Tree):
     initialize stack to contain Tree.root()
     while stack is not empty:
         p = stack.pop()
         perform 'action' for p
         for each child 'c' in Tree.children(p):
             stack.push(c)

This will search through all the nodes of tree whether binary or not. To implement search and return.. modify the algorithm accordingly.

Upvotes: 1

Vogel612
Vogel612

Reputation: 5647

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.

Upvotes: 6

Meena Chaudhary
Meena Chaudhary

Reputation: 10665

There are a few options to consider for your DFS algorithm:

  1. Firstly, use Backtracking algorithm to do a DFS search.
  2. If using Backtracking add only leftChild while traversing downwards. Otherwise reverse the order in which you push() node's children onto the Stack i.e rightChild right and then leftChild.
  3. Again if using Backtracking, avoid cycles by creating a variable nodeVistited which will be set to true once a node has been pushed on stack. Not needed otherwise. Try with these changes or let me know I will post code for DFS.

Upvotes: -3

Xline
Xline

Reputation: 812

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.

Upvotes: 2

abhi5306
abhi5306

Reputation: 134

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

Upvotes: 2

Related Questions