--Is this an example of breadth first or depth first seach?

Question

Here is a simple function to traverse the entire document object model. I was tying to understand if this is breadth first or depth first and how to understand why:

var traverseDOM = function () {
  function traverse (parent) {
    // mark 1
    _(parent.childNodes).forEach((child) => {
      traverse(child);
    }
    // mark 2
  }
  traverse(document.body);
}

It appears to be depth first search from this related SO Post.

It can be further classified according to wikipedia.

InOrder, PreOrder, and PostOrder.

Execute it by hand, and see what order it processes the nodes in the tree. — Barmar, Aug 24 '17 at 20:50
Is the question on whether you understand DFS or BFS, or you just want to understand this specific example? — stevenlacerda, Aug 24 '17 at 20:52
@pedromss It's traversing a DOM, which is a hierarchy and doesn't allow circularities. — Barmar, Aug 24 '17 at 20:52
It will go "down" a level before it goes across the same level (traversing siblings). Therefore, it is depth-first. — , Aug 24 '17 at 20:54
@Barmar if this person thinks that DFS is this he/she may want to use it in the context of circular graphs and then oh well.. Was just pointing out something that wasn't explicit. — pedromss, Aug 24 '17 at 20:59
@stackoverflow Yes, that's true. For mark1 vs mark2, that could be called "pre-order" vs "post-order" DFS, see https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search — Bergi, Aug 24 '17 at 21:07
@pedromss Both DFS and BFS will loop infinitely on a circular graph, unless you add checks for revisiting a node. That's an orthogonal issue. — Barmar, Aug 24 '17 at 23:07

Marvin · Answer 1 · 2017-08-24T22:33:38.127

Consider the following tree:

You start with traverse(1):

traverse(1)

And after "mark 1" the method will start looping over all child nodes, calling traverse for each. The first, traverse(1.1), will "barge in on the execution":

traverse(1)
traverse(1.1)

As traverse(1.1) hits "mark 1", it will start to proceed its children and call traverse(1.1.1):

traverse(1)
traverse(1.1)
traverse(1.1.1)

Since "1.1.1" does not have any children, traverse(1.1.1) reaches "mark 2" and the execution flow will return to the forEach loop of the parent method traverse(1.1):

traverse(1)
traverse(1.1)

The loop continues and traverse will be called for the second child, "1.1.2":

traverse(1)
traverse(1.1)
traverse(1.1.2)

After both children of "1.1" have been processed, traverse(1.1) reaches "mark 2" and the execution flow is now back in the forEach loop of traverse(1):

traverse(1)

Proceeding with "1.2":

traverse(1)
traverse(1.2)

I'll stop here, but you should get the hang of it. What you can see is that "1.1.1" and "1.1.2" are visited before "1.2", making it a depth-first search. A breadth-first search would visit "1.2" and "1.3" before "1.1.1".

what tool you used to draw the graph? great explanation and great job! — deblocker, Aug 26 '17 at 21:49

Raman · Answer 2 · 2017-08-24T21:24:53.773

1

As Eugene mentioned, it is an example of Depth First Search algorithm. If you notice in line#4, it is using recursion and passing the first child it has searched:

    `traverse(child);`

and this line is being called for each child in the parent node.

UPDATE: Adding a comment for clarity: "as soon as it gets "first" child, it calls traverse function again on that child, forcing the system to go down until it hits a node."

edited Aug 24 '17 at 21:24

answered Aug 24 '17 at 20:56

Raman

44
7

While correct this isn't good reasoning, or it isn't fully reasoned out. Breadth-first search will also traverse child nodes. – Aug 24 '17 at 20:57
hitting the first child is the first thing it does each time, therefore it gets deep asap – dandavis Aug 24 '17 at 21:06
@Amy, as soon as it gets "first" child, it calls traverse function again on that child, forcing the system to go down until it hits a node. Let me update my answer. Thanks for pointing it out. – Raman Aug 24 '17 at 21:23
@user3815252 don't explain it to *me*. flesh out the reasoning in your answer. – Aug 24 '17 at 21:23

--Is this an example of breadth first or depth first seach?

2 Answers2