Skip to content

Instantly share code, notes, and snippets.

@bertiespell
Last active December 24, 2018 10:38
Show Gist options
  • Save bertiespell/b034ac7b314a9006e7da986bc9d750df to your computer and use it in GitHub Desktop.
Save bertiespell/b034ac7b314a9006e7da986bc9d750df to your computer and use it in GitHub Desktop.
A depth first searching function :)
function depthFirstSearch(tree, searchTerm) { // accepts standard object
if (typeof searchTerm === 'number') {
searchTerm = String(searchTerm);
}
if (typeof searchTerm !== 'string') {
return null;
}
const objKeys = Object.keys(tree);
for (let key of objKeys) {
if (key === searchTerm) {
return tree[key];
}
if (typeof tree[key] === 'object') {
const returnValue = depthFirstSearch(tree[key], searchTerm);
if (returnValue !== null) {
return returnValue;
}
}
}
return null;
}
// ------- Alternative graph implementation --------
function depthFirstGraph(graph, searchTerm) {
for (let key in graph) {
function searchKey(graphKey) {
if (graphKey === searchTerm) {
return {
value: graph[graphKey]
};
} else {
const arr = graph[graphKey];
if (!arr.length) return null
for (let index in arr) {
const result = searchKey(arr[index]);
if (result && result.value) return result;
}
}
}
const result = searchKey(key);
if (result && !Array.isArray(result)) return result.value;
}
return null;
}
const graph = {
a: ['b', 'c'],
b: ['d', 'e', 'f'],
c: ['g'],
d: [],
e: [],
f: [],
g: ['h'],
h: []
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment