BFS and DFS

Breadth First Search and how to apply it on Javascript DOM

1. Introduction

BFS focusing on exhausting all options at current level/depth, thus is good for maze.

DFS focusing on using recursion to reach to the end of options, track it and go back to origin and repeat.

BFS uses a queue while BFS uses a stack.

So we can either use native JS array or write our own queue and stack

2. Similar Approach of BFS

The classic BFS approach for a binary tree is to use a queue and push each queue entry’s children onto the end of the queue.

This way, the queue will run to the end of the row/level before moving onto the next level.

The steps should be

1. while loop for incrementing depth when inner loop end
2. Inner loop, looping through the current Node in queue.
3. We will Do FIFO and pop the first Node, and immediately add, verify potential feasible child Nodes to end
4. Marked the new visited Node as visited ( Usually use a new array to store, but you can do it in-place)
5. End the Inner Loop
6. Increment Depth

Confused? I will explain the step 3 more before I show you the code.

3. What are we doing in step 3?

We are trying to go through every feasible options(Nodes),

by adding every possible options on to end of Array,

Starting with a root, and go to its children, and its grand children.

Pop the first one and then verified, so eventually no element can be in queue.

And we can store a “depth” variable to keep track the change of queue.

4.Examples

Given a DOM tree, flatten it into an one dimensional array, in the order of layer by layer, like below.

function flatten(root) {
  // your code here
  if(!root) return []
  const queue = [root] // Step 1 We start with the root node
  const res = []  // In this case we want to store the result array, could be depth
  while(queue.length){
    const node = queue.shift()  // We pop the top element
    node && queue.push(...node.children)  // and push its children
    res.push(node)		// store the result
  }
  return res
}