Binary Tree Implementation

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    //Code here
      const node = new Node(value);
      if(!this.root){
          this.root = node;
          return this;
      }

      let currentNode = this.root;

      while(true){
          if(currentNode.value > value){
              if(!currentNode.left){
                  currentNode.left = node;
                  return this;
              }
              
              currentNode = currentNode.left
          } else {
            if(!currentNode.right){
                  currentNode.right = node;
                  return this;
            }
              
            currentNode = currentNode.right  
          }
      }      
  }
  lookup(value){
    //Code here
      if(!this.root){
          return null;
      }

      let currentNode = this.root;

      while(true){
          if(currentNode.value == value){
              return currentNode;
          }
          
          if(currentNode.value > value){
              if(!currentNode.left){
                  return null;
              }
              
              currentNode = currentNode.left
          } else {
            if(!currentNode.right){
                  return null;
            }
              
            currentNode = currentNode.right  
          }
      }  
  }
  // remove
  breadthFirstSearch(){
      let currentNode = this.root;
      let list = [];
      let queue = [];
      queue.push(currentNode);
      while(queue.length > 0){
          currentNode = queue.shift();
          list.push(currentNode.value);
          if(currentNode.left){
              queue.push(currentNode.left);
          } 

          if(currentNode.right){
              queue.push(currentNode.right);
          }
      }

      return list;
  }
  breadthFirstSearchRecursive(queue, list){
      if(!queue.length){
          return list;
      }

      let currentNode = queue.shift();
      list.push(currentNode.value);
      if(currentNode.left){
          queue.push(currentNode.left);
      }
      if(currentNode.right){
          queue.push(currentNode.right);
      }

      return this.breadthFirstSearchRecursive(queue, list);
  }
  
  dfsInOrder(currentNode, list){

    if(currentNode.left){
      this.dfsInOrder(currentNode.left, list);
    }
    
    list.push(currentNode.value);
    
    if(currentNode.right){
      this.dfsInOrder(currentNode.right, list);
    }

    return list;
  }

  dfsPostOrder(currentNode, list){

    if(currentNode.left){
      this.dfsPostOrder(currentNode.left, list);
    }
    
    if(currentNode.right){
      this.dfsPostOrder(currentNode.right, list);
    }
    
    list.push(currentNode.value);

    return list;
  }
  
  dfsPreOrder(currentNode, list){
      list.push(currentNode.value);

      if(currentNode.left){
        this.dfsPreOrder(currentNode.left, list);
      }

      if(currentNode.right){
        this.dfsPreOrder(currentNode.right, list);
      }

      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)

tree.lookup(170);

tree.breadthFirstSearch();

tree.breadthFirstSearchRecursive([tree.root], []);

tree.dfsPostOrder(tree.root, [])

//JSON.stringify(traverse(tree.root))

//     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;
}