Created
May 19, 2021 16:27
-
-
Save basil2style/c9abbade5736779fcc5333462d8347d0 to your computer and use it in GitHub Desktop.
breadthFirstSearch on a Tree . Check out https://levelup.gitconnected.com/finding-the-shortest-path-in-javascript-pt-1-breadth-first-search-67ae4653dbec
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
| /* | |
| 10 | |
| / \ | |
| 4 17 | |
| / \ / \ | |
| 1 9 12 18 | |
| let tree = { | |
| "10": { | |
| value: "10", | |
| left: "4", | |
| right: "17", | |
| }, | |
| "4": { | |
| value: "4", | |
| left: "1", | |
| right: "9", | |
| }, | |
| "17": { | |
| value: "17", | |
| left: "12", | |
| right: "18", | |
| }, | |
| "1": { | |
| value: "1", | |
| left: null, | |
| right: null, | |
| }, | |
| "9": { | |
| value: "9", | |
| left: null, | |
| right: null, | |
| }, | |
| "12": { | |
| value: "12", | |
| left: null, | |
| right: null, | |
| }, | |
| "18": { | |
| value: "18", | |
| left: null, | |
| right: null, | |
| }, | |
| }; | |
| */ | |
| let BreadthFirstSearch = (tree, rootNode, searchValue) => { | |
| //make queue | |
| let queue = []; | |
| //populate it with node that will be the root of your search | |
| queue.push(rootNode); | |
| //search the queue until it is empty | |
| while (queue.length > 0) { | |
| // assign the top of the queue to variable currentNode | |
| let currentNode = queue[0]; | |
| // if currentNode is the node we're searching for, break & alert | |
| if (currentNode.value === searchValue) { | |
| console.log('Found it'); | |
| return; | |
| } | |
| // if currentNode has a left child node, add it to the queue. | |
| if (currentNode.left !== null) { | |
| queue.push(tree[currentNode.left]); | |
| } | |
| // if currentNode has a right child node, add it to the queue. | |
| if (currentNode.right !== null) { | |
| queue.push(tree[currentNode.right]); | |
| } | |
| // remove the currentNode from the queue. | |
| queue.shift(); | |
| } | |
| console.log('Sorry, no such node found :('); | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment