Depth First Search(InOrder,PreOrder,PostOrder)

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      let currentNode = this.root;
      while(true){
        if(value < currentNode.value){
          //Left
          if(!currentNode.left){
            currentNode.left = newNode;
            return this;
          }
          currentNode = currentNode.left;
        } else {
          //Right
          if(!currentNode.right){
            currentNode.right = newNode;
            return this;
          } 
          currentNode = currentNode.right;
        }
      }
    }
  }
  lookup(value){
    if (!this.root) {
      return false;
    }
    let currentNode = this.root;
    while(currentNode){
      if(value < currentNode.value){
        currentNode = currentNode.left;
      } else if(value > currentNode.value){
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        return currentNode;
      }
    }
    return null
  }
  // remove
  remove(value){
      if(!this.root){
          return false;
      }
      let currentNode=this.root;
      let parentNode=null;
      while(currentNode){
          if(value<currentNode.value){
              parentNode=currentNode;
              currentNode=currentNode.left;
          }
          else if (value>currentNode.value){
              parentNode=currentNode;
              currentNode=currentNode.right;
          }
          else if(value===currentNode.value){
              //if it has no right child
              if(currentNode.right===null){
                  if(parentNode===null){
                      this.root=currentNode.left
                  }else{
                      if(currentNode.value<parentNode.value){
                          parentNode.left=currentNode.left;
                      }
                      else if(currentNode.value>parentNode.value){
                          parentNode.right=currentNode.left;
                      }
                  }
              }
              else if(currentNode.right.left===null){
                  currentNode.right.left=currentNode.left;
                  if(parentNode===null){
                      this.root=currentNode.right;
                  }
                  else{
                      if(currentNode.value<parentNode.value){
                          parentNode.left=currentNode.right;
                      }
                      else if(currentNode.value>parentNode.value){
                          parentNode.right=currentNode.right
                      }
                      else{
                          let leftmost=currentNode.right.left;
                          let leftmostParent=currentNode.right;
                          while(leftmost!==null){
                              leftmostParent=leftmost;
                              leftmost=leftmost.left;
                          }
                          leftmostParent.left=leftmost.right;
                          leftmost.left=currentNode.left;
                          leftmost.right=currentNode.right;
                          
                          if(parentNode===null){
                              this.root=leftmost;
                          }
                          else{
                              if(currentNode.value<parentNode.value){
                                  parentNode.left=leftmost;
                              }
                              else if(currentNode.value>parentNode.value){
                                  parentNode.right=leftmost;
                              }
                          }
                      }
                    return false;
                  }
              }
          }
      }
  }
  
  breadthFirstSearch(){
      let currentNode=this.root;
      let list=[];
      let queue=[];
      queue.push(currentNode);
      
      while(queue.length>0){
          currentNode=queue.shift();
          list.push(currentNode);
          if (currentNode.left){
              queue.push(currentNode.left);
          }
          if(currentNode.right){
              queue.push(currentNode.right);
          }
      }
      return list;
  }
  
  DFSInOrder(){
      return traverseInOrder(this.root,[]);
  }
  
  DFSPreOrder(){
      return traversePreOrder(this.root,[]);
  }
  DFSPostOrder(){
      return traversePostOrder(this.root,[]);
  }
}

 function traverseInOrder(node,list){
      if(node.left){
          traverseInOrder(node.left,list);
      }
      list.push(node.value);
      if(node.right){
          traverseInOrder(node.right,list);
      }
      return list;
  }
  
  function traversePreOrder(node,list){
      list.push(node.value);
      if(node.left){
          traversePreOrder(node.left,list);
      }
      if(node.right){
          traversePreOrder(node.right,list);
      }
      return list;
  }
  
  function traversePostOrder(node,list){
      if(node.left){
          traversePostOrder(node.left,list);
      }
      if(node.right){
          traversePostOrder(node.right,list);
      }
      list.push(node.value);
      return list;
  }

const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
// JSON.stringify(traverse(tree.root))
tree.lookup(15);
tree.lookup(7);
console.log(tree.DFSInOrder());
console.log(tree.DFSPreOrder());
console.log(tree.DFSPostOrder());

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}