Non-recursive depth first search algorithm [closed]

Question

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

Savagery

What exactly is a "non binary tree"? A graph? – Pickaxe

@Bart Kiers A tree in general, judging by the tag. – Vaseline

@Bart a tree can have any number of children. There's B tree, "2,3,4 tree", or lots of other types too. – Souffle

Depth first search is a recursive algorithm. The answers below are recursively exploring nodes, they are just not using the system's call stack to do their recursion, and are using an explicit stack instead. – Badalona

@biziclop, @glowcoder, yes, you're probably right. Thanks. – Pickaxe

@Null Set No, it's just a loop. By your definition, every computer program is recursive. (Which, in a certain sense of the word they are.) – Vaseline

@Null Set: A tree is also a recursive data structure. – Fruity

@Vaseline I wouldn't call it just a loop. It's a loop and a stack! – Badalona

@Null Set That doesn't really matter in this case. Depending on which meaning of the word "recursion" you apply, either every computer program is recursive (computable) or just the ones that have functions that call themselves directly or indirectly. – Vaseline

aaz's answer below avoids using a stack, possible only when nodes have links to their parents – Hopi

most answers here use stack, but if you're going to use memory to keep track might as well use recursive and let call stack do that. I thought advantage of loop function over recursive was that you could go over large data without having to load it up in memory twice. – Never

@MuhammadUmer the main benefit of iterative over recursive approaches when iterative is considered less readable is that you can avoid max stack size / recursion depth constraints that most systems / programming languages implement to protect the stack. With an in memory stack your stack is only limited by the amount of memory your program is permitted to consume, which typically allows for a stack much larger than the max call stack size. – Onetoone

Answer 1

DFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

BFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.append( currentnode.children );
  //do something
}

The symmetry of the two is quite cool.

Update: As pointed out, take_first() removes and returns the first element in the list.

Vaseline

+1 for noting how similar the two are when done non-recursively (as if they're radically different when they're recursive, but still...) – Souffle

And then to add to the symmetry, if you use a min priority queue as the fringe instead, you have a single-source shortest path finder. – Rayleigh

BTW, the .first() function also removes the element from the list. Like shift() in many languages. pop() also works, and returns the child nodes in right-to-left order instead of left-to-right. – Fran

Does this have any disadvantage to the recursive approach? E.g., stack size here is O(depth * degree), instead of just O(depth) with the recursion. But then each element of recursion's stack is at least O(degree) I think? – Strader

It seems it can be easily modified from a tree to a general graph easily - just need to mark which nodes have been visited. Can this also work on an implicit graph? Can this work if I need post-order processing, rather than pre-order that it is doing as is? – Strader

@Strader This is just a simple pseudocode example, but it's easy to change it to avoid copying all the children in the queue (for example you just copy the parent node and the index of the next child). It works on implicit graphs if you replace .children with a call to the edge generation function. I haven't thought about post-order processing but I don't think this approach has much practical use in general, recursive code is bound to be easier to read, it's more of a demonstration of a principle. – Vaseline

A deque or linked list are good structures for this, due to the first-element removal. See this answer on deque performance as compared with list. – Collencollenchyma

@Nick The most efficient would be a something an array-backed list that wrapped around. So removing the first element would be as simple as nulling it out and incrementing the start pointer. You would need to expand the array if it wrapped around far enough to overwrite the start node, but that's not a problem, since it's an amortized cost. – Souffle

@Souffle Or you could use a stack :) – Vaseline

@Vaseline Yes, that would be ever so slightly more efficient, but then you're not 'taking from the front'. Well, unless you redefine front :-) – Souffle

@Souffle What you described looks suspiciously like a stack, except with a stack you're just hoping that it won't bump into anything as it grows. – Vaseline

@Vaseline My described structure runs into the same problem of growing that your typical array-based stack runs into. What my point was saying was that an array based structure is superior to a node-based structure, but that in order to not make it a "stack" you would need to wrap around the front. There's no denying that an array based stack (not my concoction) is the simplest, most efficient structure. – Souffle

IMO, the DFS algo is slightly incorrect. Imagine 3 vertices all connected to each other. The progress should be: gray(1st)->gray(2nd)->gray(3rd)->blacken(3rd)->blacken(2nd)->blacken(1st). But your code produces: gray(1st)->gray(2nd)->gray(3rd)->blacken(2nd)->blacken(3rd)->blacken(1st). – Secluded

@learner I might be misunderstanding your example but if they're all connected to each other, that's not really a tree. – Vaseline

@biziclop, yes. It is not a tree. So this doesn't apply to non-tree graphs? – Secluded

@learner The question was about trees. And in a tree it's guaranteed that you never encounter the same node twice, which is something this algorithm exploits when it throws away every node right after processing. If you're doing BFS and DFS on non-tree graphs, you must keep track of nodes already visited somehow to avoid visiting the same node twice. (Or for all eternity, if the graph has a cycle.) – Vaseline

@Vaseline I have an idea. I'm wondering that if my method can work for a graph with cycyles. I can just avoid to add dulplicated nodes to the stack. What I will do is to mark all the neighbors of the node which are popped out and add a if (nodes are not marked) to judge whether it is approapriate to be pushed to the stack. No matter the node is going to be visited or visited already. I just mark them to avoid the dulplicated push. Can this work? – Sidonnie

@Stallman It's easier if you simply keep a list of all the nodes visited. – Vaseline

@Vaseline How can I know if the node is visited? If I only record the nodes to be visited, it still can't handle graph with cycles.Btw, I have spent lots of time in searching similar approach. But their psuedo-code are so abstract or complex. – Sidonnie

@Vaseline DFS is incorrect, there is no backtracking. You are moving deeper but never climb back, it will not work with more then 1 child. – Diver

@AlexBurtsev As already mentioned, first() returns and removes the first element. – Vaseline

So that root gets put and then immediately taken out? – Quintan

@Quintan Yes, that's what kickstarts the whole process. – Vaseline

Is there a simple way (adding one or two lines) to return the path given a specific destination node in this code? – Eger

"The symmetry of the two is quite cool."... except that the "DFS" version has no backtracking stage, which means that it is not "DFS" at all (at least in Dijkstra sense of the term). DFS is a major fundamental algorithm that serves as a backbone of many other algorithms built on top of it. And large number of those algorithms rely on the backtracking properties of true DFS. This "DFS" cannot be uses for that purpose. – Cloe

@AnT That is true but if you need backtracking (which, given that we're talking about trees only, is unlikely), it's trivial to modify it to have it. Obviously at that point the symmetry disappears but I specifically wanted to concentrate on the similarities of the traversals themselves. – Vaseline

This answer applies to trees only (as was asked for). However, a graph will iterate the neighbors of a node. In this case, you need to take an additional step to avoid re-tracing your path. Before adding a neighbor to the stack, check to make sure it's not the previous currentnode. You'll need another check to avoid retracing through cycles. These two checks could be merged into a single check to make sure a neighbor has not yet been traversed. – Perfection

This is just beautiful. Of course I had to optimize it because adding and removing the first item is inefficient in most languages (ended up pushing a reversed list of children and popping from the back). In python you can use a deque. I tried a few deque packages in JavaScript and none were as fast as my solution. – Ghats

This answer changed my life – Todtoday

Answer 2

You would use a stack that holds the nodes that were not visited yet:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile

Fruity

@Fruity I'm wondering that if it is a graph with cycyles. Can this work? I think I can just avoid to add dulplicated node to the stack and it can work. What I will do is to mark all the neighbors of the node which are popped out and add a if (nodes are not marked) to judge whether it is approapriate to be pushed to the stack. Can that work? – Sidonnie

@Stallman You could remember the nodes that you have already visited. If you then only visit nodes which you haven’t visited yet, you won’t do any cycles. – Fruity

@Fruity What do you mean by doing cycles? I think I just want the order of DFS. Is that right or not, thank you. – Sidonnie

Just wanted to point out that using a stack (LIFO) means depth first traversal. If you want to use breadth-first, go with a queue (FIFO) instead. – Monopteros

It's worth noting that to have equivalent code as the most popular @Vaseline answer, you need to push child notes in reverse order (for each node.childNodes.reverse() do stack.push(stack) endfor). This is also probably what you want. Nice explanation why it's like that is in this video: youtube.com/watch?v=cZPXfl_tUkA endfor – Ejecta

Answer 3

If you have pointers to parent nodes, you can do it without additional memory.

def dfs(root):
    node = root
    while True:
        visit(node)
        if node.first_child:
            node = node.first_child      # walk down
        else:
            while not node.next_sibling:
                if node is root:
                    return
                node = node.parent       # walk up ...
            node = node.next_sibling     # ... and right

Note that if the child nodes are stored as an array rather than through sibling pointers, the next sibling can be found as:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None

Forthright

This is a good solution because it does not use additional memory or manipulation of a list or stack (some good reasons to avoid recursion). However it is only possible if the tree nodes have links to their parents. – Hopi

Thank you. This algorithm is great. But in this version you can't delete node's memory in visit function. This algorithm can convert tree to single-linked list by using "first_child" pointer. Than you can walk through it and free node's memory without recursion. – Godden

"If you have pointers to parent nodes, you can do it without additional memory" : storing pointer to parent nodes does use some "additional memory"... – Speedy

@rptr87 if it wasn't clear, without additional memory apart from those pointers. – Sawyer

This would fail for partial trees where node is not the absolute root, but can be easily fixed by while not node.next_sibling or node is root:. – Greatly

Answer 4

Use a stack to track your nodes

Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}

Souffle

@Dave O. No, because you push back the children of the visited node in front of everything that's already there. – Vaseline

I must have misinterpreted the semantics of push_back then. – Assurgent

@Dave you have a very good point. I was thinking it should be "pushing the rest of the queue back" not "push to the back." I will edit appropriately. – Souffle

If you're pushing to the front it should be a stack. – Hypo

@Timmy yeah I'm not sure what I was thinking there. @quasiverse We normally think of a queue as a FIFO queue. A stack is defined as a LIFO queue. – Souffle

@glowcoder- Can you change from using "Queue" to using "Stack?" I almost downvoted this because using a queue gives a BFS rather than a DFS (though you're treating to queue more like a stack, so it works out correctly) – Windblown

Answer 5

An ES6 implementation based on biziclops great answer:

root = {
  text: "root",
  children: [{
    text: "c1",
    children: [{
      text: "c11"
    }, {
      text: "c12"
    }]
  }, {
    text: "c2",
    children: [{
      text: "c21"
    }, {
      text: "c22"
    }]
  }, ]
}

console.log("DFS:")
DFS(root, node => node.children, node => console.log(node.text));

console.log("BFS:")
BFS(root, node => node.children, node => console.log(node.text));

function BFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...nodesToVisit,
      ...(getChildren(currentNode) || []),
    ];
    visit(currentNode);
  }
}

function DFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...(getChildren(currentNode) || []),
      ...nodesToVisit,
    ];
    visit(currentNode);
  }
}

Lilas

Answer 6

While "use a stack" might work as the answer to contrived interview question, in reality, it's just doing explicitly what a recursive program does behind the scenes.

Recursion uses the programs built-in stack. When you call a function, it pushes the arguments to the function onto the stack and when the function returns it does so by popping the program stack.

Epner

With the important difference that the thread stack is severely limited, and the non-recursive algorithm would use the much more scalable heap. – Ceraceous

This is not just a contrived situation. I've used techniques like this on a few occasions in C# and JavaScript to gain significant performance gains over existing recursive call equivelants. It is often the case that managing the recursion with a stack instead of using the call stack is much faster and less resource intensive. There is a lot of overhead involved in placing a call context onto a stack vs the programmer being able to make practical decisions about what to place on a custom stack. – Vinasse

Answer 7

PreOrderTraversal is same as DFS in binary tree. You can do the same recursion 
taking care of Stack as below.

    public void IterativePreOrder(Tree root)
            {
                if (root == null)
                    return;
                Stack s<Tree> = new Stack<Tree>();
                s.Push(root);
                while (s.Count != 0)
                {
                    Tree b = s.Pop();
                    Console.Write(b.Data + " ");
                    if (b.Right != null)
                        s.Push(b.Right);
                    if (b.Left != null)
                        s.Push(b.Left);

                }
            }

The general logic is, push a node(starting from root) into the Stack, Pop() it and Print() value. Then if it has children( left and right) push them into the stack - push Right first so that you will visit Left child first(after visiting node itself). When stack is empty() you will have visited all nodes in Pre-Order.

Rolanderolando

Answer 8

Non-recursive DFS using ES6 generators

class Node {
  constructor(name, childNodes) {
    this.name = name;
    this.childNodes = childNodes;
    this.visited = false;
  }
}

function *dfs(s) {
  let stack = [];
  stack.push(s);
  stackLoop: while (stack.length) {
    let u = stack[stack.length - 1]; // peek
    if (!u.visited) {
      u.visited = true; // grey - visited
      yield u;
    }

    for (let v of u.childNodes) {
      if (!v.visited) {
        stack.push(v);
        continue stackLoop;
      }
    }

    stack.pop(); // black - all reachable descendants were processed 
  }    
}

It deviates from typical non-recursive DFS to easily detect when all reachable descendants of given node were processed and to maintain the current path in the list/stack.

Henna

Answer 9

Suppose you want to execute a notification when each node in a graph is visited. The simple recursive implementation is:

void DFSRecursive(Node n, Set<Node> visited) {
  visited.add(n);
  for (Node x : neighbors_of(n)) {  // iterate over all neighbors
    if (!visited.contains(x)) {
      DFSRecursive(x, visited);
    }
  }
  OnVisit(n);  // callback to say node is finally visited, after all its non-visited neighbors
}

Ok, now you want a stack-based implementation because your example doesn't work. Complex graphs might for instance cause this to blow the stack of your program and you need to implement a non-recursive version. The biggest issue is to know when to issue a notification.

The following pseudo-code works (mix of Java and C++ for readability):

void DFS(Node root) {
  Set<Node> visited;
  Set<Node> toNotify;  // nodes we want to notify

  Stack<Node> stack;
  stack.add(root);
  toNotify.add(root);  // we won't pop nodes from this until DFS is done
  while (!stack.empty()) {
    Node current = stack.pop();
    visited.add(current);
    for (Node x : neighbors_of(current)) {
      if (!visited.contains(x)) {
        stack.add(x);
        toNotify.add(x);
      }
    }
  }
  // Now issue notifications. toNotifyStack might contain duplicates (will never
  // happen in a tree but easily happens in a graph)
  Set<Node> notified;
  while (!toNotify.empty()) {
  Node n = toNotify.pop();
  if (!toNotify.contains(n)) {
    OnVisit(n);  // issue callback
    toNotify.add(n);
  }
}

It looks complicated but the extra logic needed for issuing notifications exists because you need to notify in reverse order of visit - DFS starts at root but notifies it last, unlike BFS which is very simple to implement.

For kicks, try following graph: nodes are s, t, v and w. directed edges are: s->t, s->v, t->w, v->w, and v->t. Run your own implementation of DFS and the order in which nodes should be visited must be: w, t, v, s A clumsy implementation of DFS would maybe notify t first and that indicates a bug. A recursive implementation of DFS would always reach w last.

Roede

Answer 10

FULL example WORKING code, without stack:

import java.util.*;

class Graph {
private List<List<Integer>> adj;

Graph(int numOfVertices) {
    this.adj = new ArrayList<>();
    for (int i = 0; i < numOfVertices; ++i)
        adj.add(i, new ArrayList<>());
}

void addEdge(int v, int w) {
    adj.get(v).add(w); // Add w to v's list.
}

void DFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
            }
        }
        System.out.println(nextChild);
    }
}

void BFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(s);// add the node to the END of the unvisited node list.
            }
        }
        System.out.println(nextChild);
    }
}

public static void main(String args[]) {
    Graph g = new Graph(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(3, 1);
    g.addEdge(3, 4);

    System.out.println("Breadth First Traversal- starting from vertex 2:");
    g.BFS(2);
    System.out.println("Depth First Traversal- starting from vertex 2:");
    g.DFS(2);
}}

output: Breadth First Traversal- starting from vertex 2: 2 0 3 1 4 Depth First Traversal- starting from vertex 2: 2 3 4 1 0

Sommers

nodesToVisit.contains(s) takes linear time in the number of elements in nodesToVisit. Alternatives include keeping track of which nodes were already visited in a boolean array with O(1) access time and O(numOfVertices) extra space. – Jejune

Answer 11

Just wanted to add my python implementation to the long list of solutions. This non-recursive algorithm has discovery and finished events.

worklist = [root_node]
visited = set()
while worklist:
    node = worklist[-1]
    if node in visited:
        # Node is finished
        worklist.pop()
    else:
        # Node is discovered
        visited.add(node)
        for child in node.children:
            worklist.append(child)

Lott

Answer 12

http://www.youtube.com/watch?v=zLZhSSXAwxI

Just watched this video and came out with implementation. It looks easy for me to understand. Please critique this.

visited_node={root}
stack.push(root)
while(!stack.empty){
  unvisited_node = get_unvisited_adj_nodes(stack.top());
  If (unvisited_node!=null){
     stack.push(unvisited_node);  
     visited_node+=unvisited_node;
  }
  else
     stack.pop()
}

Purge

Answer 13

You can use a stack. I implemented graphs with Adjacency Matrix:

void DFS(int current){
    for(int i=1; i<N; i++) visit_table[i]=false;
    myStack.push(current);
    cout << current << "  ";
    while(!myStack.empty()){
        current = myStack.top();
        for(int i=0; i<N; i++){
            if(AdjMatrix[current][i] == 1){
                if(visit_table[i] == false){ 
                    myStack.push(i);
                    visit_table[i] = true;
                    cout << i << "  ";
                }
                break;
            }
            else if(!myStack.empty())
                myStack.pop();
        }
    }
}

Hygroscopic

Answer 14

DFS iterative in Java:

//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
    if (root == null)
        return false;
    Stack<Node> _stack = new Stack<Node>();
    _stack.push(root);
    while (_stack.size() > 0) {
        Node temp = _stack.peek();
        if (temp.data == target)
            return true;
        if (temp.left != null)
            _stack.push(temp.left);
        else if (temp.right != null)
            _stack.push(temp.right);
        else
            _stack.pop();
    }
    return false;
}

Matchlock

Question explicitly asks for a non binary tree – Hygrometric

You need a visited map to avoid infinite loop – Cleavable

Answer 15

Using Stack, here are the steps to follow: Push the first vertex on the stack then,

1. If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack.
2. If you can’t follow step 1, then, if possible, pop a vertex off the stack.
3. If you can’t follow step 1 or step 2, you’re done.

---

Here's the Java program following the above steps:

public void searchDepthFirst() {
    // begin at vertex 0
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // if no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
}

Epineurium

Answer 16

Pseudo-code based on @biziclop's answer:

• Using only basic constructs: variables, arrays, if, while and for
• Functions getNode(id) and getChildren(id)
• Assuming known number of nodes N

---

NOTE: I use array-indexing from 1, not 0.

Breadth-first

S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        S[ last+i ] = children[i]
    end
    last = last+n
    cur = cur+1

    visit(node)
end

Depth-first

S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        // assuming children are given left-to-right
        S[ cur+i-1 ] = children[ n-i+1 ] 

        // otherwise
        // S[ cur+i-1 ] = children[i] 
    end
    cur = cur+n-1

    visit(node)
end

Thermo

Answer 17

Here is a link to a java program showing DFS following both reccursive and non-reccursive methods and also calculating discovery and finish time, but no edge laleling.

    public void DFSIterative() {
    Reset();
    Stack<Vertex> s = new Stack<>();
    for (Vertex v : vertices.values()) {
        if (!v.visited) {
            v.d = ++time;
            v.visited = true;
            s.push(v);
            while (!s.isEmpty()) {
                Vertex u = s.peek();
                s.pop();
                boolean bFinished = true;
                for (Vertex w : u.adj) {
                    if (!w.visited) {
                        w.visited = true;
                        w.d = ++time;
                        w.p = u;
                        s.push(w);
                        bFinished = false;
                        break;
                    }
                }
                if (bFinished) {
                    u.f = ++time;
                    if (u.p != null)
                        s.push(u.p);
                }
            }
        }
    }
}

Full source here.

Atul

Answer 18

Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
    Node node = stack.pop();
    System.out.print(node.getData() + " ");

    Node right = node.getRight();
    if (right != null) {
        stack.push(right);
    }

    Node left = node.getLeft();
    if (left != null) {
        stack.push(left);
    }
}

Triparted