/* 

                    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()