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

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.

Blog

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

Edwin

Breadth-First Search

Steps to implement

Join Our Newsletter. No Spam, Only the good stuff.

Related