Last active
February 29, 2020 03:53
-
-
Save 20k-ultra/07fca8c645d37a51ec5b09aac0fc1211 to your computer and use it in GitHub Desktop.
Depth First search algorithm in JS
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
class Node { | |
constructor(val) { | |
this.data = val; | |
this.left = null; | |
this.right = null; | |
} | |
getChildren() { | |
let children = [] | |
if (this.left) { | |
children.push(this.left) | |
} | |
if (this.right) { | |
children.push(this.right) | |
} | |
return children | |
} | |
} | |
class BinarySearchTree { | |
constructor() { | |
this.root = null; | |
} | |
insertNode(val) { | |
var node = new Node(val) | |
var currentNode; | |
if (!this.root) { | |
this.root = node; | |
} else { | |
currentNode = this.root; | |
while (currentNode) { | |
if (val < currentNode.data) { | |
if (!currentNode.left) { | |
currentNode.left = node; | |
break; | |
} else { | |
currentNode = currentNode.left; | |
} | |
} else if (val > currentNode.data) { | |
if (!currentNode.right) { | |
currentNode.right = node; | |
break; | |
} else { | |
currentNode = currentNode.right; | |
} | |
} else { | |
console.log('Ignoring this value as the BST supposed to be a tree containing UNIQUE values'); | |
break; | |
} | |
} | |
} | |
} | |
} | |
function depthFirstSearch(tree) { | |
let nodes = [] // list of nodes | |
getNodes(tree.root.getChildren()) // start recursion with no level_index so default is used | |
function getNodes(level, level_index = 0) { | |
level.forEach(node => { // loop threw nodes in the level | |
if (Array.isArray(nodes[level_index])) { | |
nodes[level_index].push(node.data) // if node already in this level then add | |
} else { | |
nodes[level_index] = [node.data] // first node in this level so create array | |
} | |
// // repeat with this nodes children and descend 1 level | |
getNodes(node.getChildren(), level_index + 1) | |
}); | |
} | |
return nodes | |
} | |
var BST = new BinarySearchTree(); | |
BST.insertNode(8); | |
BST.insertNode(3); | |
BST.insertNode(10); | |
BST.insertNode(1); | |
BST.insertNode(6); | |
BST.insertNode(14); | |
BST.insertNode(4); | |
BST.insertNode(7); | |
BST.insertNode(13); | |
let nodes = depthFirstSearch(BST) | |
console.log(nodes) // [ [ 3, 10 ], [ 1, 6, 14 ], [ 4, 7, 13 ] ] | |
// return list of values from nodes on the 3rd level with comma delimiter | |
console.log(nodes[2].join(",")) // 4,7,13 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment