7. BFS & DFS

BFS

Breadth First Search

• Queue
  : go same level node first and go deeper

• push root node
• pop root node
  • push children nodes From Left to Right
• pop child node one by one and…
  • push children nodes from child (((repeat)))

queue.enqueue(this);
while (queue.length > 0) {
    current = queue.dequeue();
    children = current.children;
    for (let i=0; i<children.length; i++) {
    	queue.enqueue(children[i]);
    }
}

DFS

Depth First Search

• Stack
  : go down to the leaf node first and move on to the other children

• push root node
• pop root node
  • push children nodes From Left To Right
• pop child node and…
  • push children nodes of child (((repeat)))
• pop the leaf node
  • pop other leaf nodes on the same level / push children nodes of the node on the same level
• pop parent node and move on (((repeat)))

stack.push(this);
while (stack.length > 0) {
  current = stack.pop();
  children = current.children;
  for (let i=0; i<children.length; i++) {
    stack.push(children[i]);
  }
}