HackerRank- Trees: Is This a Binary Search Tree

HackerRank- Trees: Is This a Binary Search Tree

---

해당 트리가 이진 탐색 트리인지 확인 하는 문제이다.

단순히 특정 노드의 자식들 값이 부모보다 작은지 큰지를 가지고 판단할 경우 아래의 경우에 문제가 발생 한다.

이유는 4의 경우 root 보다 큰대도 불구하고 자식 노드의 자식으로 분류되어 있다.
즉, 더 윗 부분의 부모 노드에서 판단하는 부분이 제외 되기 때문에 문제가 발생 한다.

방법1

• 재귀적으로 최소 최대 값을 확인하며 루프를 도는 방법
• 일단 데이터에 음수가 없다는 가정에서 출발 한다.

def checkBST(root):
    return(check_in_order(root,[-1]))
    
def check_in_order(root,prev):
    result = True
    if root.left is not None:
        result &= check_in_order(root.left,prev)
    if prev[0] >= root.data:
        return False
    prev[0] = root.data
    if root.right is not None:
        result &= check_in_order(root.right,prev)
    return result

방법2

• Inorder traversal을 해서 확인하는 방법.
• 올바른 Binary Search라면 출력이 순차적이게 된다.
• 해당 문제에서 보면 중독된 노드는 이진탐색트리로 허용하지 않으니 그 문제에 대한 해결을 필요로 한다.

""" Node is defined as
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
"""

def checkBST(root):
    # traversal by inOrder 
    resList = []
    resList = inOrder(root,resList)
    sortedList = sorted(resList)
    
    if len(set(resList)) != len(resList):
        return False
    
    if len([i for i, j in zip(resList, sortedList) if i == j]) == len(resList):
        return True
    else:
        return False
    
def inOrder(node,resList):
    if node.left is not None:
        resList = inOrder(node.left, resList)
    resList.append(node.data)
    if node.right is not None:
        resList = inOrder(node.right, resList)
    return resList