Implementation of DFS using iterative approach in java

Question

I have seen a lot of implementations of DFS using a boolean variable named visited, which I don't wish to use in my code. While considering a scene where we have a Node class that holds the reference to left and right nodes corresponding to its children and data which can be any Object, can this method be applicable to Binary Trees to calculate dfs ? I have a scenario where I don't have a adjacency list or matrix.

Is the following code a good implementation of DFS ? Is the time complexity of the code O(n) ?

public void dfsForTree(BSTNode root) {
    Stack<BSTNode> s = new Stack<BSTNode>();
    BSTNode node;
    if (root == null) {
        return;
    }
    s.push(root);
    while (!s.isEmpty()) {
        node = s.pop();
        System.out.println(node.getData());
        if (node != null) {

            if (node.getRight() != null) {
                s.push(node.getRight);
            }
            if (node.getLeft != null) {
                s.push(node.getLeft);
            }

        }
    }
}

BSTNode class implementation:

public class BSTNode {

private BSTNode left;
private BSTNode right;
private int data;

/* Constructor */
public BSTNode(int n) {
    left = null;
    right = null;
    data = n;
}
/* Function to set left node */

public void setLeft(BSTNode n) {
    left = n;
}
/* Function to set right node */

public void setRight(BSTNode n) {
    right = n;
}
/* Function to get left node */

public BSTNode getLeft() {
    return left;
}
/* Function to get right node */

public BSTNode getRight() {
    return right;
}
/* Function to set data to node */

public void setData(int d) {
    data = d;
}
/* Function to get data from node */

public int getData() {
    return data;
}

Possible duplicate of [Iterative tree walking](http://stackoverflow.com/questions/754439/iterative-tree-walking) — ivan_pozdeev, Oct 11 '15 at 20:30

score 0 · Answer 1 · edited May 23 '17 at 10:29

A sure tell of an iterative tree walk is it requires an "up" link on a node (or saves them) to be able to backtrack. You do just this - only saving not "up" links but directly next links to go after backtracking. On the other hand, there are no interdependencies between steps. See Is this function recursive even though it doesn't call itself? for how to distinguish iterative and disguised recursive.

Also see Iterative tree walking for an overview of the algorithms.

Now, for computational complexity. The principle can be found at Big O, how do you calculate/approximate it?.

You do:

process every node
- exactly once
push & pop nodes from the stack
- each node is also pushed and popped exactly once

So, indeed, it's O(N).

Implementation of DFS using iterative approach in java

1 Answers1