Skip to content

Instantly share code, notes, and snippets.

@Prottoy2938
Last active March 12, 2020 06:24
Show Gist options
  • Save Prottoy2938/305bee363eecb76da5377a32353548f6 to your computer and use it in GitHub Desktop.
Save Prottoy2938/305bee363eecb76da5377a32353548f6 to your computer and use it in GitHub Desktop.
`Breadth-first search` algorithm for Binary Search Tree
//breadth_First_Search
//This method, visits tree's node horizontally and pushes them. It uses queue to keep track of its work.
//Example: 10
// 6 15
// 3 8 20
//result node would be =[10, 6, 15, 3, 8, 20]
//The Breadth-first search algorithm that's shown in here, is for data structures like `Binary Search Tree`.
const breadth_First_Search = tree => {
let node = tree.root;
let queue = [];
let visited = [];
queue.push(node);
while (queue.length) {
node = queue.shift();
visited.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return visited;
};
//EXAMPLE===================================================================
const exampleBST = {
"root": {
"value": 10,
"right": {
"value": 15,
"right": {
"value": 20,
"right": null,
"left": null
},
"left": null
},
"left": {
"value": 6,
"right": {
"value": 8,
"right": null,
"left": null
},
"left": {
"value": 3,
"right": null,
"left": null
}
}
}
}
const totalNode = breadth_First_Search(exampleBST); //returns [10, 6, 15, 3, 8, 20]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment