Breadth-First Search
This is an algorithm for traversing a tree where the traversing starts from a selected node normally the root and the traversing happens layerwise from left to right.
In the diagram above if we traversed the tree and stored the results in an array the result array would be [0,1,2,3,4,5,7]
Steps to implement
- Create a node variable set it to the root property
- Create data and queue variables set them to an empty array or List.
- Add the node variable at the end of the queue.
- Iterate while the queue is no empty, on each Iteration set the node the first node remove from the queue array. Add the node value property to the data array then check if a left property exists on the node if it does add it to the queue check if the right property exists and add it to the node.
The JavaScript code implementation is as below BFS:
class Node{ constructor(val){ this.val = val; this.left = null; this.right = null; } } class BST{ constructor(){ this.root = null; } insert(val){ let newNode = new Node(val); if(!this.root){ this.root = newNode; }else{ let current = this.root; while(true){ if(val < current.val){ if(current.left === null){ current.left = newNode; return this }else{ current = current.left; } }else{ if(current.right === null){ current.right = newNode; return this }else{ current = current.right } } } } } find(val){ let current = this.root; let found = false; while(current && !found){ if(val < current.val){ if(current.val === val){ found = true; return current; }else{ current = current.left; } }else{ if(current.val === val){ found = true; return current; }else{ current = current.right; } } } return 'not found' } BFS(){ let data=[]; let queue=[]; let node= this.root; queue.push(node); while(queue.length){ node = queue.shift(); data.push(node.val); if(node.left)queue.push(node.left); if(node.right)queue.push(node.right); } return data } } let tree = new BST(); tree.insert(100); tree.insert(200); tree.insert(150); tree.insert(80); tree.insert(90); tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(180); tree.insert(190); console.log(tree,BFS()) In python :-
class Node: def __init__(self,val): self.val = val self.left = None self.right = None class BST: def __init__(self): self.root= None def insert(self, val): newNode = Node(val) if self.root == None: self.root= newNode else: current = self.root while True: if val< current.val: if current.left == None: current.left = newNode return self else: current= current.left else: if(current.right == None): current.right = newNode return self else: current = current.right def find(self, val): current= self.root found = False while current and not found: if val < current.val: current = current.left elif val > current.val: current= current.right else: found = True if(not found): return "not found" return current def bfs(self): node = self.root data = [] queue = [] queue.append(node) while len(queue)!= 0: node = queue.pop(0) data.append(node.val) if(node.left): queue.append(node.left) if(node.right): queue.append(node.right) return data bst = BST() bst.insert(100) bst.insert(200) bst.insert(150) bst.insert(175) bst.insert(160) bst.insert(180) bst.insert(75) bst.insert(50) bst.insert(65) bst.insert(40) bst.insert(55) bst.insert(20) print(bst.bfs()) Next we will take a look at depth first search preorder.
Top comments (0)