class Tree {
  constructor(value) {
		// constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    this.children = [];
  }
  // tree = new Tree(1)
  // tree = { value : 1, children : [{ value : 2, children : [] }, { value : 3, children : [] }] }

	// 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
		// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
		// TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

  // 트리 안에 인자로 받은 value가 포함되어 있는지 확인하는 메서드
  contains(value) {
    // base case
    if (this.value === value) {
      return true;
    }
	// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색.(재귀 필요)
    // recursive case
    for (let t of this.children) {
      if(t.contains(value)) {
        return true;
      }
    }	
	// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
    return false;
  }
}

class BinarySearchTree {
  constructor(value) {
		// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
    this.value = value;
    this.left = null;
    this.right = null;
  }

	// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
  insert(value) {
		// 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 합니다.
		// 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣습니다.
    if (value < this.value) {
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      } else { // this.left가 빈 값이 아니라면
				// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
				// TIP: 재귀함수를 사용합니다.
        this.left.insert(value);
      }
		// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
    } else if (value > this.value) {
      if (this.right === null) {
        this.right = new BinarySearchTree(value);
      } else {
				// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
				// TIP: 재귀함수를 사용합니다.
        this.right.insert(value);
      }
		//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
    } else {
      // 아무것도 하지 않습니다.
    }
  }
  // 앞서 구현했던 트리에 비해 이진 탐색 트리는 입력 값에 따라 위치가 정해지므로 입력값과 트리 노드의 값의 크기를 비교

	// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
		// TODO: 값이 포함되어 있다면 true를 반환하세요.
    if (value === this.value) {
      return true;
    }
		// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
    if (value < this.value) {
			// TODO: 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
      if( this.left !== null && this.left.value === value) {
        return true;
      }
			// TODO:일치하지 않다면 왼쪽 노드로 계속 이동하여 다시 탐색합니다. 
      // if(this.left.contains()) {
      //   return true;
      // }
      this.left.contains()
    }
		// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
    if (value > this.value) {
			// TODO: 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
      if( this.left !== null && this.right.value === value) {
        return true;
      }
			// TODO:일치하지 않다면 오른쪽 노드로 계속 이동하여 다시 탐색합니다. 
      // if(this.right.contains()) {
      //   return true;
      // }
      this.right.contains()
    }
		// 없다면 false를 반환합니다.
    return false;
  }

	/*
	트리의 순회에 대해 구현을 합니다.
  지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
  전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
	*/

	// 전위 순회 : 뿌 왼 오 (우선순위 : 뿌리->왼쪽 자식->오른쪽 자식 순)
  preorder(callback) {
		callback(this.value);
    if (this.left) {
      this.left.preorder(callback);
    };
    if (this.right) {
      this.right.preorder(callback);
    };
  }

	// 중위 순회 : 왼 뿌 오 (우선순위 : 왼쪽자식-> 뿌리-> 오른쪽 자식)
  inorder(callback) {
		if (this.left) {
      this.left.inorder(callback);
    }
    callback(this.value)
    if (this.right) {
      this.right.inorder(callback);
    }
  }

	// 후위 순회 : 우선순위 : 왼쪽자식->오른쪽 자식-> 뿌리
  postorder(callback) {
		if (this.left) {
      this.left.postorder(callback);
    }
    if (this.right) {
      this.right.postorder(callback);
    }
    callback(this.value);
  }
}

// binarySearch 함수
// 파라미터 - target : 찾으려는 타겟, dataArray : 데이터 배열
function binarySearch(target, dataArray) {
    // 최소값
    let low = 0;
    // 최대값 
    let high = dataArray.length - 1;
    // 최대값이 최소값 보다 크면 반복
    while (low <= high) {
        // 중간값 구하기
        let mid = Math.floor((high + low) / 2);
        // dataArray의 중간값
        let guess = dataArray[mid];
        // 만약 추정한게 target과 같다면 
        if (guess === target) {
            // 추정 값 리턴
            return guess;
            // 그렇지 않고 추정 값이 target보다 크다면
        } else if (guess > target) {
            // 최대 값은 = 중간값 -1;
            high = mid - 1;
        } else {
            // 추정값이 target보다 작다면
            // 최소값은 = 중간값 +1;
            low = mid + 1;
        }
    }
    // 찾으려는 target이 없다면 
    return undefined;
}