Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* Depth first search and Breadth first search traverals in JavaScript
* This example uses a binary tree with left and right nodes
* by theptrk <github.com/theptrk>
*/
function Node(value, opts = {}) {
this.value = value
this.left = opts.left ? opts.left : null
this.right = opts.right ? opts.right : null
}
var root = new Node('a', {
left: new Node('b'),
right: new Node('c', {
left: new Node('d', {
left: new Node('f'),
right: new Node('g', {
left: null,
right: new Node('h')
})
}),
right: new Node('e')
})
})
/**
* The tree looks like this:
*
* node('a')
* node('b') node('c')
* node('d') node('e')
* node('f') node('g')
* node('h')
*/
/**
* Depth first search: prototype function (method) : recursive
* This function will short circuit on the check based on left nodes
* Note that we need to check for the existence of the left and right nodes
*/
Node.prototype.dfs = function(target) {
if (this.value === target) {
return true;
}
// Optimization: here we evaluate left before right,
// Note this is NOT done lazily in JavaScript
var inLeft = this.left === null ? false : this.left.dfs(target);
if (inLeft) {
// we optimistically return from evaluating left node
return inLeft
}
var inRight = this.right === null ? false : this.right.dfs(target);
if (inRight) {
return inRight
}
return false;
}
/**
* Depth first search: prototype function (method) : iterative
* This is solved by using a stack for its LIFO property
*/
Node.prototype.dfsIterative = function(target) {
var stack = [];
// our first node in the stack is the current node, typically the root
stack.push(this);
while (stack.length > 0) {
// we process nodes from the "top" of the stack
var lifoNode = stack.pop();
if (lifoNode.value === target) {
return true;
}
// note, since we are using lifo, our right nodes must
// be push first (left nodes will be on top of the stack)
if (lifoNode.right) {
stack.push(lifoNode.right);
}
if (lifoNode.left) {
stack.push(lifoNode.left);
}
}
// if we reach this point, all child nodes from this node have been visited
return false;
}
/**
* Breadth first search: prototype function (method) : iterative
*/
Node.prototype.bfs = function(target) {
var queue = [];
// our first node in the stack is the current node, typically the root
queue.push(this)
while (queue.length > 0) {
// we process nodes from the "front" of the queue
// an optimized queue back by a linked list can be used here
fifoNode = queue.shift()
if (fifoNode.value === target) {
return true;
}
// note, since we are using fifo, our left nodes must pushed first;
// immediate left nodes will be processed before immediate right notes
if (fifoNode.left) {
queue.push(fifoNode.left)
}
if (fifoNode.right) {
queue.push(fifoNode.right)
}
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.