Skip to content

Instantly share code, notes, and snippets.

@jvalen
Created September 25, 2015 00:39
Show Gist options
  • Save jvalen/5b65f4382e0933d5a58f to your computer and use it in GitHub Desktop.
Save jvalen/5b65f4382e0933d5a58f 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