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

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

  insert(value){
    const newNode = new Node(value);
    if(!this.root) return this.root = newNode;
    return this.insertRecursive(this.root, newNode);
  }
  
  delete(value){
    if(!this.root) return this.root;
    return this.deleteRecursive(this.root, value);
  }

  insertRecursive(node, newNode){
    if(!node) return newNode; // 왼쪽이나 오른쪽 자식노드가 없다면 그냥 노드 넣기
    if(node.value > newNode.value) node.left = this.insertRecursive(node.left, newNode); // 새 노드의 값이 더 작다면, 왼쪽노드의 값과 비교해보기위해 재귀함수 전달
    if(node.value <= newNode.value) node.right = this.insertRecursive(node.right, newNode); // 새 노드의 값이 더 크거나 같다면, 오른쪽노드의 값과 비교해보기위해 재귀함수 전달
    return node;
  }

  deleteRecursive(node, value){
    if(!node) return; // 노드가 없다면 그냥 종료
    if(node.value > value){ // 지우려는값보다 현재노드의 값이 더 크다면, 왼쪽노드의 값과 비교하기위해 재귀함수 전달
      node.left = this.deleteRecursive(node.left, value);
      return node; // 재귀함수 탈출구
    }
    if(node.value < value){ // 지우려는값보다 현재노드의 값이 더 작다면, 오른쪽노드의 값과 비교하기위해 재귀함수 전달
      node.right = this.deleteRecursive(node.right, value);
      return node; // 재귀함수 탈출구
    }

    // 지우려는 값과 현재 노드의 값이 동일하여 지우려는 대상일 경우
    if(!node.left && !node.right) return node = null; // 자식이 없을때는 그냥 삭제
    if(!node.left && node.right) return node = node.right; // 오른쪽자식만 있다면, 오른쪽자식 끌어올리기
    if(node.left && !node.right) return node = node.left; // 왼쪽자식만 있다면, 왼쪽자식 끌어올리기

    // 둘다 가지고있을 경우
    let changeTarget = node.left; // 현재 노드의 왼쪽자식을 기준으로 가장 오른쪽에있는 Leaf노드를 찾음(현재 노드의 값보단 작은 두번째로 큰 값)
    while(changeTarget.right) changeTarget = changeTarget.right;
    node.value = changeTarget.value; // 현재 노드의 값을 찾은 값으로 변경
    changeTarget.value = value; // 찾은 값을 현재노드의 값으로 변경
    node.left = this.deleteRecursive(node.left, value); // 현재 노드의 왼쪽자식을 기준으로 하여 지우려는 값을 삭제하는 재귀함수 진행 후, 새롭게 왼쪽자식트리 생성
    return node; // 재귀함수 탈출구
  }
}

const tree = new Tree();
tree.insert(6);
tree.insert(10);
tree.insert(7);
tree.insert(4);
tree.insert(12);
tree.insert(15);
tree.insert(1);
tree.insert(3);
tree.insert(2);
tree.insert(5);
tree.delete(6)
console.log(tree);