Breadth First Search — An Overview

source

Overview

Tree Data Structure Example

Breadth First Search. “What Is It?”

Depth First Search Example
Breadth First Search Example
Breadth For Search Demonstration

Queues, Queues, Queues

Queue Illustration

Implementing the Breadth First Search

the following creates the structure of the binary tree by adding the name of the node and its children (as an array)constructor(name) {
//this creates the node as name
this.name = name;//this creates the node's children for the binary tree
this.children = []
}
addChild(name){
//pushes the newly created nodes in to the children array.
this.children.push(new Node(name));
//return the created branch
return this
}
breadthFirstSearch(stashArray) {
//create a queue array to store queues. This can be done by creating an array with just the root node as a starting point .
const queue = [this]
//add the tree branches until the queue's length is 0 or less! (which in this case wont be until the very tip of the branch)
while (queue.length > 0) { //currently iterated queue element will be the first element of the queue
const current = queue.shift()
//add the name of the node to the Stashed/Visited Array as you're traversing through the tree stashArray.push(current.name);
//for each child of the node in the current element of the queue, add the children associated to the node in to the queue
for (const child of current.children) {
queue.push(child)
}
}
//finally return the array with all the Stashed/Visited elements
return stashArray
}

Time/Space Complexity

Recursive Solution?? — “no”

Concept Summary

Hi, i’m a software engineer based in NYC!