Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function BinarySearchTree() {
- function Node(value) {
- this.value = value;
- this.left = null;
- this.right = null;
- }
- this.root = null;
- this.addNode = function(value) {
- let node = new Node(value);
- if (!this.root) {
- this.root = node;
- } else {
- insertNode(this.root, node);
- }
- }
- function insertNode(currentNode, newNode) {
- if (newNode.value < currentNode.value) {
- if (!currentNode.left) {
- currentNode.left = newNode;
- } else {
- insertNode(currentNode.left, newNode);
- }
- } else {
- if (!currentNode.right) {
- currentNode.right = newNode;
- } else {
- insertNode(currentNode.right, newNode);
- }
- }
- }
- //Breadh First Traversal method that accepts a callback argument which will be used on each node we traverse
- this.breadthFirstTraversal = function(callback) {
- //Queue data structure to hold our nodes
- let queue = [];
- //nextNode binding to keep track of the current node we are traversing.
- let nextNode;
- //First push the root node into the queue.
- queue.push(this.root);
- //While we are still traversing the tree and there are still children nodes in the queue.
- while(queue.length>0) {
- //Remove the first indexed item from the queue array and store it in nextNode.
- nextNode = queue.shift();
- //If the current node we are traversing has a left child, put it into the queue.
- if(nextNode.left) {
- queue.push(nextNode.left);
- }
- //If the current node we are traversing has a right child, put it into the queue.
- if(nextNode.right) {
- queue.push(nextNode.right);
- }
- //Perform the callback argument on the node's value.
- callback(node.value);
- //Now if the queue still has nodes in it, the loop will continue to perform the callback and then stop when there are
- //no more child nodes.
- }
- }
- }
- let tree = new BinarySearchTree();
- tree.addNode(3);
- tree.addNode(5);
- tree.addNode(14);
- tree.addNode(11);
- tree.addNode(25);
- tree.addNode(2);
- tree.breadthFirstTraversal(function log(value) {
- console.log(value);
- });
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement