// class for node
class Node{
  constructor(value){
    this.value = value
    this.left = null
    this.right = null
  }
}

// BST

class BST{
  constructor(value){
    this.root = new Node(value)
    this.count =0
  }

  // insert
  insert (value) {
    this.count++
    const newNode = new Node(value)
    const searchTree = (node) =>{
      //If value is less then node value go left
      if(value < node.value){
        if(!node.left){
          node.left = newNode
        }else
        {
          searchTree(node.left)
        }
      }
      //If value is greater then node value go right
      else if(value > node.value){
        if(!node.right){
          node.right = newNode
        }else
        {
          searchTree(node.right)
        }
      }
    }
    searchTree(this.root)
  }

  //min
  min(){
    let currentNode = this.root
    while(currentNode.left){
      currentNode = currentNode.left
    }
    return currentNode.value
  }

  //max
  max(){
    let currentNode = this.root
    while(currentNode.right){
      currentNode = currentNode.right
    }
    return currentNode.value
  }

  // contains
  contains(value){
    let currentNode = this.root

    while(currentNode){
      if(value === currentNode.value){
        return true;
      }
      if(value < currentNode.value){
        currentNode = currentNode.left
      }else{
        currentNode = currentNode.right
      }
    }
    return false
  }

  // left root right
  dfsInOrder(){
    let result =[]
    const traverse = node =>{
      if(node.left) traverse(node.left);
      result.push(node.value)
      if(node.right) traverse(node.right);
    }
    traverse(this.root)
    return result
  }

  //root left right
  dfsPreOrder(){
    let result =[]
    const traverse = node =>{
      result.push(node.value)
      if(node.left) traverse(node.left);
      if(node.right) traverse(node.right);
    }
    traverse(this.root)
    return result
  }

  //left right root
  dfsPostOrder(){
    let result =[]
    const traverse = node =>{
      if(node.left) traverse(node.left);
      if(node.right) traverse(node.right);
      result.push(node.value)
    }
    traverse(this.root)
    return result
  }

  //bfs
  bfs(){
    let result =[]
    let queue = []

    while(queue.length){
      let currentNode = queue.unshift()
      result.push(currentNode.value)
      if(currentNode.left){
        queue.push(currentNode.left)
      }
      if(currentNode.right){
        queue.push(currentNode.right)
      }
    }
    return result
  }
}

const myBST = new BST(8)
myBST.insert(3)
myBST.insert(10)
myBST.insert(1)
myBST.insert(6)
myBST.insert(14)
myBST.insert(13)
myBST.contains(13)
myBST.contains(23)
myBST.dfsInOrder()
console.log(myBST)