DFS in Binary Tree

Question

I have written this code for DFS in a binary tree and would like improvements on it.

    // Method 1: Recursive DFS 
public static boolean DFS(Node root, int k){    
    if(root == null){
        return false;
    } else if (root.data == k){
        return true;
    } else {
        return DFS(root.left, k) || DFS(root.right, k);
    }
}   
//=============================================================================     
        // Method 2: DFS using stack 
        public static boolean DFS2(Node root, int k){
            if(root == null){
                return false;
            }
            Stack<Node> stack = new Stack<Node>();
            stack.push(root);
            while(!stack.isEmpty()){
                Node current = stack.pop();
                if(current.data == k){
                    return true;                        //Found the value!
                }
                if(current.right != null){
                    stack.push(current.right);
                }
                if(current.left != null){      // As we want to visit left 
                stack.push(current.left);  //child first, we must push this node last
            }
        }
        return false;                               // Not found
    }
//============================================================================      
    // Method 3: DFS by marking visited nodes - using stack 
    public static boolean DFS4(Node root, int k) {
        if(root == null){
            return false;
        }
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node current = stack.pop(); 
            if(current.data == k){
                return true;
            }
            current.visited = true;         
            if (current.right != null && current.right.visited == false) {
                stack.push(current.right);
            }           
            if (current.left != null && current.left.visited == false) {
                stack.push(current.left);
            }
        }
        return false;
    }
//============================================================================      
// Method 4: DFS (search) by putting visited nodes in a hash set - using stack 
public static boolean DFS5(Node root, int k) {
    if(root == null){
        return false;
    }
    Stack<Node> stack = new Stack<Node>();
    HashSet<Node> hs = new HashSet<Node>();
    stack.push(root);       
    while (!stack.isEmpty()) {
        Node current = stack.pop(); 
        hs.add(current);
        if(current.data == k){
            return true;
        }                   
        if (current.right != null && !hs.contains(current.right)) {
            stack.push(current.right);
        }           
        if (current.left != null && !hs.contains(current.left)) {
            stack.push(current.left);
        }
    }
    return false;
}

Answer 1

General

Your methods all use a C-like system for the tree Nodes. In Java, the tree should be an Object, and the Node class should not be publicly visible. In other words, you should have something like:

public class BinaryTree {
     private static class Node {
         private Node left, right;
         private int value;
         .....
     }

     private Node root = null;

     public searchDFS1(int value) {
         .....
     }

     public searchDFS2(int value) {
         .....
     }

     public searchDFS3(int value) {
         .....
     }

Note how the methods are no longer static, and their implementation can have private access to the root instance (if any).

DFS1

public static boolean DFS(Node root, int k){    
    if(root == null){
        return false;
    } else if (root.data == k){
        return true;
    } else {
        return DFS(root.left, k) || DFS(root.right, k);
    }
}

This is a typical implementation of a recursive DFS. I see no issues with the implementation other than the static implementation. Typically, you would do it like:

public boolean DFS(int k) {
    return recurse(root, k);
}

private boolean recurseDFS(Node node, int k) {

    if(node == null) {
        return false;
    }
    return node.data == k || recurseDFS(node.left, k) || recurseDFS(node.right, k);

} 

I would not worry too much about the stack overflow. Java typically has 10's of thousands of levels it will manage before overflow. On a reasonably balanced tree this would be more than enough.

DFS2

Again with the static, but the rest of the implementation looks fine. The Stack based system is a head-scratcher, but it works well. It allows for the stack to simulate a recursive approach, and that's what we would expect.

Your use of isEmpty() is good, and often I see people using size() != 0, so nice there.

DFS3

You messed up your naming, why is //DFS3 got the method name DFS4? Consistency please.

THis one using a visited marker on the node is a real problem. The code is no longer reentrant, and you have to reset each node before you can call the function again.

DFS4 (or 5, depending).

Using a HashSet is an OK option, but it requires a lot more space to manage. Additionally, it depends on the hashcode and equals methods, so would be slower.

I would avoid it.

Answer 2

I would retain DFS2 and get rid of all the other implementations. Reason: DFS is cool also, but as it is recursive, you may get a stack overflow on trees with large maximum depth. What comes to DFS4 and DFS5, since you work on trees, there is no need for visited set as trees are acyclic. Also, what comes to coding style, I would love seeing an empty line before and after each if or while statement; I think that adds up to readability.

Answer 3

A few minor points on top of @coderodde's excellent answer.

The formatting is sloppy throughout. Use the auto-reformat function of your favorite IDE. Code is read far more often than it is written, it's worth the investment to write it nicely optimized for readability.

The parameter names root is a bit misleading in a recursive method traversing the nodes, as most of the time the node in the parameter will not be the root of the tree. node would be better.

Keep in mind that method names should use camelCase.

The discrepancy in the numbering in comments and method names of confusing, for example method 2 is named dfs2 but method 3 is named dfs4. This is a good example demonstrating the importance of good practices in commenting. You could give these methods more descriptive names instead of adding comments that might later become outdated, obsolete.

Answer 4

if (current.right != null && current.right.visited == false) {
    stack.push(current.right);
}           
if (current.left != null && current.left.visited == false) {
    stack.push(current.left);
}

The above are mutually exclusive so you should use else if to make the logic more explicit.

Answer 5

I want to add more of a description for the fact that one doesn't need to check for the nodes that are already visited in this problem.

A tree, according to Wikipedia:

a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

In DFS, we mark the visited nodes to avoid checking them twice and getting into an infinite loop. When we run into a visited node in an undirected graph via DFS, we actually have already put it in the stack and popped it (because we do it to every node we visit) and add its neighbours to the stack. Now we're trying to do the same to its neighbours, so when we reach a previously popped node, there is a path from that node to itself with a length of at least one, thus the graph contains a loop.

If the algorithm goes on and adds the visited node to the stack, it would eventually pop out again and add its neighbours. Then again we run into it and we have to repeat the process an infinite number of times.

But in a tree, there is no loop, so checking for already visited nodes is redundant.