## DEV Community is a community of 697,485 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

# Binary Tree Part 3 'Breadth-First Search' JavaScript and Python

Edwin
Python , JavaScript and Elixir Developer
・3 min read

## 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

1. Create a node variable set it to the root property
2. Create data and queue variables set them to an empty array or List.
3. Add the node variable at the end of the queue.
4. 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`.