BFS and DFS in Binary Search Tree
Tags: hacktoberfest, javascript
Published: 2020-10-22 11:36:38

    /* 

                        Example For Binary Search Tree

                                  __10__
                                /        \  
                               5         13
                              / \       / \
                             2   7     11 16 
                            / \   \         \
                           1  3   9         18

    */

    class Node {
        constructor(value){
            this.length = 0;
            this.value = value;
            this.left = null;
            this.right = null;

        }
    }
    class BinarySearchTree {
        constructor(){
            this.root = null;
        }


        // Insert a New value in tree 
        insert(value) {
            var newNode = new Node(value);
            if(this.root === null) {
                this.root = newNode;
                return this;
            } else {
                var current = this.root;
                while(true) {
                    if(value < current.value) {
                        if(current.left === null) {
                            current.left = newNode;
                            console.log(` ->   ${current.value}  left value -> ${value} added `)
                            return this;    
                        } else {
                            current = current.left;
                        }
                    } else if(value > current.value) {
                        if (current.right === null) {
                            current.right = newNode;
                            console.log(` ->   ${current.value}  right value -> ${value} added `)
                            return this;
                        } else {
                            current = current.right;
                        }
                    } 
                    if(current.value == value) {
                        console.log(` ->  ${value} is  Duplicate value Please Enter Unique Value `)
                        return;
                    }
                }
            }
        }

     // find The Value in tree
        find(value) {
               if(this.root === null) return false;
               var current = this.root,
                   found = false;
               while(current && !found) {
                   if(value < current.value) {
                       current = current.left;
                   } else if (value > current.value) {
                       current = current.right;
                   } else {
                       console.log(` ->   Founded Successfully -> ${value}`);
                       return current;
                   }
               }
               if(!found) console.log(` ->   Not Founded -> ${value}`);
               return current;
        }

     // Same as no find
        contains(value) {
           if(this.root === null) return false;
           var current = this.root,
               found = false;
           while(current && !found) {
               if(value < current.value) {
                   current = current.left;
               } else if (value > current.value) {
                   current = current.right;
               } else {
                   console.log(` ->   Founded Successfully -> ${value}`);
                   return current;
               }
           }
           if(!found) console.log(` ->   Not Founded -> ${value}`);
           return current;
       }


        /* 

                            Example For BREADTH FIRST SEARCH List

                      first ->        __10__
                                    /        \  
                     second ->     6         15
                                  / \         \
                     third ->    3   8        20

        */
       BFS() {
           var node = this.root,
               data = [],
              queue = [];
           queue.push(node);

           while(queue.length) {
              node = queue.shift()
              data.push(node.value);
              if(node.left) queue.push(node.left);
              if(node.right) queue.push(node.right);
           }
           console.log(` ->   BFS -> BREADTH FIRST SEARCH List is -> ${data}`);
           return data;
       }


        /* 

                            Example For DEPTH FIRST SEARCH List in PreOrder

                     Third ->         __10__
                                    /        \  
                     Second ->     6         15
                                  / \         \
                    First ->     3   8        20

        */
       DSFPreOrder(){
           var data = [];
           function traverse(node) {
               data.push(node.value);
              if(node.left) traverse(node.left);
              if(node.right) traverse(node.right);
           }
           traverse(this.root);
           console.log(` ->   DSF -> Pre Order List is -> ${data}`)
           return data
       }

        /* 

                            Example For DEPTH FIRST SEARCH List in PostOrder

                          sixth ->    __10__
                                    /        \  
                         Third ->  6         15 <- Fiveth
                                  / \         \
                        First -> 3   8 <-     20 <- Fourth
                                        |
                                Second _|

        */
        DSFPostOrder() {
            var data = [];
            function traverse(node) {
              if(node.left) traverse(node.left);
              if(node.right) traverse(node.right);
              data.push(node.value);
            }
            traverse(this.root);
           console.log(` ->   DSF -> Post Order List is -> ${data}`)
            return data;
        }

        DSFinOrder() {
            var data = [];
            function traverse(node) {
              node.left && traverse(node.left);
              data.push(node.value);
              node.right && traverse(node.right);
            }
            traverse(this.root);
           console.log(` ->   DSF -> In Order List is -> ${data}`)
            return data;
        }
    }

    var tree = new BinarySearchTree();
    tree.insert(10)
    tree.insert(6)
    tree.insert(15)
    tree.insert(3)
    tree.insert(8)
    tree.insert(20)
    console.log(" ");
    tree.BFS()
    tree.DSFPreOrder()
    tree.DSFPostOrder()
    tree.DSFinOrder()