DFS in binary tree and graph

Question

I am confused by DFS in binary tree and graph. In my understanding, DFS for binary tree is similar to PreOrder traversal? DFS in graph is very different? please help clarify this concept in binary tree and DFS. I know in binary tree, we can do DFS like this:

public static List<int> postorder(TreeNode root)
{
    List<int> res = new List<int>();
    traverse1(root, res);
    return res;
}

public static void traverse1(TreeNode root, List<int> res)
{
    if (root == null)
        return;    

    traverse1(root.left, res);             
    traverse1(root.right, res);
    res.Add(root.val); 
}

What about in graph? Can we do the similar way?

Fede Fede · Accepted Answer · 2015-12-01T23:32:18

It's basically the same.

To help with the understanding, I think it's better to transition from binary trees to general purpose trees, and finally to graphs.

DFS and BFS are just techniques for traversing trees and graphs. The difference between them is in which order siblings and children of a given node are visited. In a DFS, all children of a given node are visited before traversing the next sibling.

So in a binary tree that means that all descendants of the left child of a node X are visited before visiting the right child of X.

Now if you think in general trees, each node has a list of children, and not just a left and right child. So in a DFS in a general tree, all descendants of the first child of a node X are visited before visiting the second child of X, and all the descendants of the second child of X are visited before visiting the third child of X, and so on.

The thing with DFS and trees, is that you know you'll eventually hit a leaf, and the recursion will return to the caller (or halt with a stack overflow, but that's a subject for another time). With graphs you don't have that guarantee. The graph may have cycles, or perhaps there are vertices with multiple incoming edges. As I mentioned earlier, DFS is just a technique, not an algorithm per se, so what you do is adapt the technique to the problem you are solving. If in the problem you are solving you are not interested in visiting a vertex more than once, or you are not interested in iterating indefinitely in a cycle (or until you hit a stack overflow), then you have to add some kind of control code that allows you to break from those situations.

The general structure of a DFS over a graph could be something like:

void DFS(G<V,E> g, V v, Set<V> visited)
{
    if (visited.Contains(v))
        return;
    visited.Add(v);
    // do something interesting here?
    foreach (w in g.getEdges(v))
        DFS(g, w, visited);
    // uncomment this to allow visiting vertices more than once, and just avoid cycles.
    // visited.Remove(v);
}

DFS in binary tree and graph

3 Answers