Skip to content

Instantly share code, notes, and snippets.

@ccnixon
Forked from jvalen/depthFirstSearcher.js
Created October 10, 2015 15:36
Show Gist options
  • Save ccnixon/972e137938b3d95212e1 to your computer and use it in GitHub Desktop.
Save ccnixon/972e137938b3d95212e1 to your computer and use it in GitHub Desktop.
Depth-first searcher: Depth-first search through a tree of nodes. It returns the given name node.
/**
* Depth-first search tree
* @param {string} nodeName - Name of the node to find
* @param {object} tree - Node example: {name: 'a', children: [nodeA, nodeB, ...]}
* @return {object} Returns the node with the given name
*/
function depthFirstSearch(nodeName, tree) {
if (tree.name === nodeName) {
return tree; //Node found
} else {
var children = tree.children;
if (children !== null) {
var result;
for (var i = 0; i < children.length; i++) {
result = depthFirstSearch(nodeName, children[i]);
if (result !== undefined) { //If the node has been found
return result; //Return the node
}
}
}
}
}
/**
* Depth-first search tree usage example
*/
var sampleTree = {
name: 'a',
children: [
{
name: 'b',
children: [
{
name: 'd',
children: null
},
{
name: 'e',
children: null
},
{
name: 'f',
children: null
}
]
},
{
name: 'c',
children: [
{
name: 'g',
children: [
{
name: 'h',
children: null
}
]
}
]
}
]
};
console.log('Node with name: "g": ');
console.log(depthFirstSearch('g', sampleTree));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment