[python3] 783. Minimum Distance Between BST Nodes

풀이 일자: 23.02.17

난이도: [Easy]

분류: [Tree, BST]

문제 내용

BST의 root가 주어졌을 때  BST 내부의 노드 간의 차 중에서 가장 작은 값을 리턴하는 문제이다.

 

[BST란?]

BST란 Binary Search Tree의 축약어로 우리말로는 이진탐색트리라고 한다. 

탐색 대상이 주로 배열인데 이를 이진 탐색트리로 변환한다면 데이터의 삽입, 삭제 등 데이터 조작에 강점을 가지게 된다,

=> 특징으로는 root를 기준으로 root보다 작은 수는 왼쪽 node, 큰 수는 오른쪽 node에 있는 것을 확인할 수 있다.

 

 

문제 해결 흐름

1. 트리가 나왔고 노드 간의 차이를 일단 알아야 하므로 Tree를 순회하는 알고리즘을 생각해봐야 한다.

→ 일반적인 Tree 순회 알고리즘으로는 DFS와 BFS가 존재할 것이고 이 문제에서는 BFS는 별로 좋지 않을 것이다.

 

2. Tree 순회 방법은?

→ 이진 트리 순회 방법은 크게 전위, 중위, 후위 순회가 존재하는데 현재 left.val < root.val  < right.val의 형태를 가지고 있는게 BST이기 때문에 이 순서대로 탐색을 진행하는 전위 순회가 유리하겠다.

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:

        arr = list();
        ans = 100001;

        def inOrder(root: Optional[TreeNode], arr: List[int]) -> List[int]:
            if root.left:
                arr = inOrder(root.left, arr);
            arr.append(root.val);
            if root.right:
                arr = inOrder(root.right, arr);
            return arr;

        arr = inOrder(root, arr);
        for i in range(len(arr)-1):
            ans = min(ans, arr[i+1] - arr[i]);

        return ans;

=> 일반적인 전위 순회를 이용한 방법으로 node의 value를 담을 list를 사용하여 Memory의 사용량이 상대적으로 높은 것을 확인할 수 있다.

 

Time Complexity: O(N)

시간복잡도는 Tree의 모든 노드를 순회해야하기에 Tree node의 갯수만큼 시간복잡도가 나올 것이다.

 

Space Complexity: O(N)

Tree의 모든 노드의 값을 저장하기 때문에 Tree node의 갯수만큼 공간복잡도가 나올 것이다.

 

 

다른 해결 방식

1. 위의 알고리즘에서 Memory를 많이 사용했는데 list를 사용하지 않고도 풀 수 있는 방법을 생각해보자.

→ 이전 노드를 전역변수로 설정하거나 파라미터로 받아서 바로바로 차를 구하자

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:

    ans = float("inf");
    prev = None;

    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def inOrder(root: Optional[TreeNode]):
            if not root:
                return;
                
            inOrder(root.left);
            if (self.prev is not None):
                self.ans = min(self.ans, root.val - self.prev.val);
            self.prev = root;
            inOrder(root.right);

        inOrder(root);
        return self.ans;

=> 리스트에 저장하지 않고 바로바로 차를 구하므로써 메모리 극한으로 아끼기 성공.

 

Time Complexity: O(N)

시간복잡도는 Tree의 모든 노드를 순회해야하기에 Tree node의 갯수만큼 시간복잡도가 나올 것이다.

 

Space Complexity: O(H)

recursive하게 처리를 하는 만큼 stack calls를 저장하기 위해 tree의 높이만큼의 Space Complexity가 존재한다. 최악의 경우는 N-1이 될 때로 한쪽으로 치우처진 사향이진트리인 경우이다.

 

=> 시간이 오래 걸리는 편으로 판단하여 다른 방법을 찾아보기도 했으나 내 코드와의 큰 차이가 없었고 코드를 시도할 때마다 80%와 20%를 왔다갔다하는 것을 볼 때 채점하는 인터프리터의 성능의 차이로 벌어진 게 아닐까라는 생각이 든다.

 

문제 링크

https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/

Minimum Distance Between BST Nodes - LeetCode