-
-
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.
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