프로그래밍 면접 문제 7 : Binary Search Tree Check

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 6 : Combine Two Strings

이 문제는 빈번하게 출제되는 면접 문제입니다. 주어진 이진 트리가 이진 탐색 트리(binary search tree)인지 확인하는 문제입니다.

가장 먼저 떠오르는 해결 방법은, 모든 노드에 대해서 해당 노드의 값이 왼쪽 자식 노드의 값과 작거나 같은지 또는 오른쪽 자식 노드의 값과 크거나 같은지 비교하는 방법입니다 (왼쪽과 오른쪽 자식 노드 모두에서 같은 값이 나올 수 있다고 가정합니다). 하지만 이 방법은 특정 노드의 조상 노드에 대해서 어떤 조건을 위반하는지 여부를 확인하지 않기 때문에 문제가 있습니다. 다음의 예제 트리는 이진 탐색 트리로 잘못 구분될 수 있고, 이 알고리즘으로는 3과 4사이의 불일치를 감지해낼 수 없습니다:

따라서, 노드가 가질 수 있는 최소, 최대 값을 계속해서 추적해야합니다. 그리고 각 노드의 값이 그 최소 값과 최대 값 사이의 값인지 확인합니다. 루트 노드는 음의 무한대 값부터 양의 무한대 값까지 어떤 숫자라도 값으로 가질 수 있습니다. 어떤 노드든 그 왼쪽 자식 노드의 값은 해당 노드의 값보다 작거나 같아야하고, 이와 비슷하게 오른쪽 자식 노드의 값은 해당 노드의 값보다 크거나 같아야 합니다. 따라서 재귀적으로 반복하는 동안 현재 값을 왼쪽 자식 노드의 다음 재귀 수행의 최대 값으로 전달하고 최소 값은 변경없이 그대로 전달합니다. 그리고 현재 값은 오른쪽 자식 노드의 다음 재귀 수행의 최소 값으로 전다하고 최대 값은 변경없이 그대로 전달합니다. 다음은 이 접근 방법에 대한 코드입니다:

class Node:
    def __init__(self, val=None):
        self.left, self.right, self.val = None, None, val
 
INFINITY = float("infinity")
NEG_INFINITY = float("-infinity")
 
def isBST(tree, minVal=NEG_INFINITY, maxVal=INFINITY):
    if tree is None:
        return True
 
    if not minVal <= tree.val <= maxVal:
        return False
 
    return isBST(tree.left, minVal, tree.val) and 
           isBST(tree.right, tree.val, maxVal)

똑같은 효율을 가진 다른 좋은 방법도 있습니다. 어떤 트리가 이진 탐색 트리인 경우, 해당 트리를 중위(inorder) 순회로 탐색하면 트리의 값이 순차적으로 정렬됩니다. 따라서, 트리를 중위 순회(inorder traverse)로 탐색한 다음 결과로 얻은 값의 순서가 순차적으로 정렬되었는지 여부를 확인합니다. 다음은 이 방법에 대한 코드입니다:

def isBST2(tree, lastNode=[NEG_INFINITY]):
    if tree is None:
        return True
 
    if not isBST2(tree.left, lastNode):
        return False
 
    if tree.val < lastNode[0]:
        return False
 
    lastNode[0]=tree.val
 
    return isBST2(tree.right, lastNode)

이 문제는 간단하지만(하지만 중요합니다) 이진 탐색 트리와 트리 탐색의 기본 개념에 대한 이해가 필요하기 때문에 개인적으로 좋아하는 문제입니다.

다음글 – 프로그래밍 면접 문제 8 : Transform Word (문자 변환)