Validate Binary Search Tree

이 포스트에서는 leetcode의 Validate Binary Search Tree 문제를 다뤄보도록 하겠다.

• 문제링크: Validate Binary Search Tree
• 솔루션: source code

1. 문제분석

주어진 문제를 간단하게 요약해보면 아래와 같다.

Binary Search Tree(이하 BST)의 루트가 주어집니다. 이 BST가 올바르게(i.e. 노드X의 왼쪽 서브트리에는 노드X보다 작은 값들만이, 오른쪽 서브트리에는 노드X보다 큰 값들만이 있도록) 구성되어 있는지를 판단하세요.

2. 가장 멍청한 풀이

섹션의 제목이 '가장 멍청한 풀이' 이기는 하지만 알고리즘을 공부할 때 가장 멍청한 풀이부터 가장 스마트한 풀이까지 사고의 흐름을 정리하는 과정은 매우 중요하다.

따라서, 이 섹션에서 '가장 멍청한 풀이' 에 대해서 꼭 한번 짚고 넘어가고자 한다.

떠올려볼 수 있는 가장 멍청한 풀이는 주어진 BST를 inorder traversal하면서 방문순서대로 노드의 값을 기록하고, 순회를 마친 후 기록된 노드들이 오름차순으로 정렬되어 있는지를 확인하는 것이다.

잠시 딴길로...
필자의 경우는 조금 더 멍청해서, 이런 생각을 하지 않고 그냥 각 노드별로 왼쪽 자식엔 자기보다 작은 값이, 오른쪽 노드에는 보자기다 큰 값이 있으면 되는거 아니야?라는 삽질을 했었다.
똑똑한 독자들은 이미 알고 있을테지만 위와 같은 아이디어에는 아래 그림과 같은 반례가 존재한다.
아래의 그림을 보면, 노드4, 노드7 모두 왼쪽에는 보다 작은 값을 갖는 노드가 있고, 오른쪽에는 큰 값을 갖는 노드가 있다.
얼핏 valid해보이지만, 노드4를 기준으로 오른쪽 서브트리에 노드3이 있기 때문에 valid한 BST이지 않다.

보다 엄밀한 정의를 좋아하는 독자들은 아마도 이런 의문을 품고 있을 것이다.

valid한 BST를 inorder traversal하면 오름차순으로 정렬된 기록이 얻어진다는 것은 알겠어. 근데 오름차순으로 정렬된 기록이 얻어졌다고해서 valid한 BST였다고 이해해도 되는걸까?

요약하면, valid한 BST를 inorder traversal하면 오름차순으로 정렬된 기록이 얻어진다의 역도 성립하는지에 대한 의문일 것이다.

이는 의외로 쉽게 증명이 가능한데, 아래의 증명을 따라가보도록하자.

1. inorder traversal를 통해 얻은 배열을 arr[0:len]이라고 하고, 이때 arr[0:len]이 오름차순으로 정렬되어 있었다고 하자(arr[x:y]는 python과 같은 언어에서처럼 개폐구간을 의미한다).
2. 임의의 원소 arr[i]$(0<=i<len)$를 골라보자.
3. 만약 BST에서 arr[i] 값을 갖는 노드가 왼쪽 서브트리를 가졌다면, 이들은 배열에서 arr[0:i] 내에 존재한다(inorder traversal을 했으므로).
4. 그런데, arr[0:len]은 정렬되어 있다는 가정이 있으므로 arr[0:i]내의 모든 값은 arr[i]보가 작은 값을 갖는다.
5. 따라서, BST에서 arr[i] 값을 갖는 노드의 왼쪽 서브트리가 있었다면, 이들은 모두 arr[i]보다 작은 값을 갖는다.
6. 오른쪽 서브트리에 대해서도 동일하게 증명할 수 있다. (증명끝)

여튼, 위에서 이야기한 아이디어를 그대로 코드로 옮기면 아래와 같다.

class Solution
{
public:
  std::vector<int> visit_log_;

  void TraverseInorder(TreeNode* root)
  {
    if (!root)
    {
      return;
    }

    TraverseInorder(root->left);
    visit_log_.push_back(root->val);
    TraverseInorder(root->right);
  }

  bool isValidBST(TreeNode* root)
  {
    visit_log_.clear();

    TraverseInorder(root);

    for (std::size_t idx = 1; idx < visit_log_.size(); ++idx)
    {
      if (visit_log_[idx - 1] >= visit_log_[idx])
        return false;
    }

    return true;
  }
};

위의 풀이는 속도를 기준으로 23%, 메모리를 기준으로 36% 정도의 백분위를 받을 수 있다.

제시한 풀이는 트리의 노드 수를 $n$이리고 할 때, inorder traversal에 $O(n)$, 얻어진 방문기록이 오름차순인지 확인하는데 $O(n)$으로 총 $O(2n)=O(n)$의 시간복잡도를 갖는다.

또한, 방문순서를 기록하기 위해서 visit_log_ 벡터를 만들어 주었으므로 O(n)의 공간복잡도를 갖음을 알 수 있다.

3. 적당히 똑똑한 풀이

이번 섹션에서는 섹션 2에서 $O(n)$이었던 공간복잡도를 $O(1)$로 만들어보려한다.

사실 잘 생각해보면, 굳이 방문순서를 전부 별도로 기록해두고 순회 종료 이후에 오름차순을 판단해줄 필요는 없다.

그저 inorder traversal을 수행하면서, 직전에 방문한 노드보다 현재 방문한 노드의 값이 더 큰지를 살피는 방식으로 섹션 2 알고리즘의 공간복잡도를 개선해보도록 하자.

class Solution
{
public:
  bool is_first_visit_ = true;
  int last_visited_number_;

  bool isValidBST(TreeNode* root)
  {
    if (!root)
    {
      return true;
    }

    if (!isValidBST(root->left))
    {
      return false;
    }

    if (!is_first_visit_ && last_visited_number_ >= root->val)
    {
      return false;
    }

    is_first_visit_ = false;
    last_visited_number_ = root->val;

    if (!isValidBST(root->right))
    {
      return false;
    }

    return true;
  }
};

별로 특별한 개선이 아님에도 불구하고, 위와 같은 풀이를 사용하면 속도 기준 98%, 메모리 기준
92%의 백분위를 받을 수 있다.

Note) 이유는 모르겠으나 이 문제에 한해 채점마다 백분위가 크게 편차가 생긴다. 랜덤하게 주어지는 인풋에 따른 문제인지, 채점서버의 상태 때문인지 모르겠으나...우선은 백분위에 너무 의미를 두지 않도록 하자.

시간복잡도가 $O(2n)$에서 $O(n)$으로 상수배 개선되는 것과 공간복잡도가 $O(n)$에서 $O(1)$로 개선되었기 때문으로 이해할 수 있다.

4. 별로지만 해볼만한 풀이

연습삼아 꼭 해보았으면 하는 욕심이 생겼던 풀이를 본 섹션에서 정리한다.

섹션 3에서의 알고리즘이 조금 아쉬운 점이라면 아마도 재귀를 빈번히 호출하는 것이 있다.

이 섹션에서는 섹션 3과 동일한 접근을 사용하되, 재귀를 풀어해쳐서 스택을 활용하는 반복으로 구현해보도록 하겠다.

tail recursion 형태를 갖는 재귀 알고리즘을 반복문 형태로 풀어해치는 것은 매우 간단하지만, inorder traversal과 같은 형태의 재귀 알고리즘을 반복문 형태로 풀어내기는 의외로 꽤나 까다롭다.

어떤 형태의 재귀 코드이건 간에 systematic하게 반복문 형태로 바꾸는 방법이 존재하기는 하나, 이 포스팅에서는 보다 정성적인 방법으로 변환을 해보았다.

systematic한 방법에 대해서는 추후에 기회가 되면 다른 포스팅에서 다뤄보도록 하겠다.

class Solution
{
public:
  bool is_first_visit_ = true;
  int last_visited_number_;

  bool isValidBST(TreeNode* root)
  {
    TreeNode* called = root;
    std::stack<TreeNode*> to_be_returned;

    while (true)
    {
      if (called)
      {
        to_be_returned.push(called);
        called = called->left;
      }
      else
      {
        if (to_be_returned.empty())
        {
          break;
        }

        TreeNode* activated = to_be_returned.top();

        if (!is_first_visit_ && last_visited_number_ >= activated->val)
        {
          return false;
        }
        is_first_visit_ = false;
        last_visited_number_ = activated->val;

        called = activated->right;

        to_be_returned.pop();
      }
    }

    return true;
  }
};

Note) 상술하였듯, 백분위가 큰 의미가 없어 이 풀이에 대한 백분위는 첨부하지 않았다. 적어도 다른 방법에 비해 크게 꿇리지 않는 풀이임을 밝힌다.