CODEWITHSUNDEEP
c#tree
mjsr
mjsr

Reputation: 7590

Confusion regarding BFS or DFS recursion in a treeview

I'm doing some procesing in a treeview, I don't use neither a stack or a queue to process all the nodes, I just do this:

void somemethod(TreeNode root){
    foreach(TreeNode item in root.Nodes)
    {
        //doSomething on item
        somemethod(item);
    }
 }

I'm a litle block right know (can't think with clarity) and I can't see what kind of tree processing I'm doing. Is this BFS or DFS or neither of them?

My clue was DFS but wasn't sure. The CLR don't do anything weird like process two siblings before passing down taking advantage of multiprocessing? That weird tough comes to my mind that clouded my judgment

Upvotes: 3

Views: 1467

Answers (2)

BrokenGlass
BrokenGlass

Reputation: 160892

You are doing a DFS (Depth first search/traversal) right now using recursion.

Its depth first because recursion works the same way as a stack would - you process the children of the current node before you process the next node - so you go for depth first instead of breadth.

Edit:

In response to your comment / updated question: your code will be processed sequentially item by item, there will be no parallel processing, no "magic" involved. The traversal using recursion is equivalent to using a stack (LIFO = last in, first out) - it is just implicit. So your method could also have been written like the following, which produces the same order of traversal:

public void SomeMethod(TreeNode root)
{
    Stack<TreeNode> nodeStack = new Stack<TreeNode>();
    nodeStack.Push(root);

    while (nodeStack.Count > 0)
    {
        TreeNode node = nodeStack.Pop();
        //do something on item
        //need to push children in reverse order, so first child is pushed last
        foreach (TreeNode item in node.Nodes.Reverse())
            nodeStack.Push(item);
    }
}

I hope this makes it clearer what is going on - it might be useful for you to write out the nodes to the console as they are being processed or actually walk through step by step with a debugger.

(Also both the recursive method and the one using a stack assume there is no cycle and don't test for that - so the assumption is this is a tree and not any graph. For the later DFS introduces a visited flag to mark nodes already seen)

Upvotes: 7

Nappy
Nappy

Reputation: 3046

Im pretty sure your example corresponds to "Depth first search", because the nodes on which you "do something" increase in depth before breadth.

Upvotes: 2

Related Questions