Created
September 25, 2015 00:39
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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