이진 탐색 트리 유효성 검사(Validating a Binary Search Tree)

References

아래 링크의 강의 중 Section 28. Validating a Binary Search Tree의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Validating a Binary Search Tree

function validate(node, min = null, max = null) {
  if (max !== null && node.data > max) {
    return false;
  }

  if (min !== null && node.data < min) {
    return false;
  }

  if (node.left && !validate(node.left, min, node.data)) {
    return false;
  }

  if (node.right && !validate(node.right, node.data, max)) {
    return false;
  }

  return true;
}

recursive function과 if문을 거치면서 입력값이 root값을 기준으로 작다면 왼쪽에 위치하고, 크다면 오른쪽에 놓이게 한다. 여기서 왼쪽 트리를 탐색할 때는 탐색 중인 왼쪽 트리의 값이 max값에 할당되어 그보다 작은 값만 왼쪽 트리에 저장되게끔 제한을 하고, 반대로 오른쪽은 min값이 바뀌어 탐색 중인 오른쪽 트리의 값보다 큰 값만이 오른쪽에 저장되게끔 한다.