Bir binary tree'nin geçerli bir Binary Search Tree olup olmadığını nasıl kontrol edersiniz?

Her düğümün yalnızca çocuklarıyla değil, tüm atalarından gelen alt ve üst sınırla karşılaştırılması gerekir. Bu yüzden özyinelemeye (low, high) aralığı taşırız.

Klasik hata

Sadece node.left.val < node.val < node.right.val kontrolü yetmez:

      5
     / \
    1   6
       / \
      3   7

Burada 3, 6'nın solunda olduğu için yerel kontrolü geçer ama kökteki 5'ten küçük olduğu için sağ alt ağaçta olamaz. Ağaç geçersizdir.

Sınır taşıyarak çözüm

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if root is None:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Inorder gezinme ile çözüm

Geçerli bir BST'nin inorder gezinmesi kesin artan bir dizi üretir. Önceki değeri tutup her adımda karşılaştırmak yeterlidir:

def is_valid_bst_inorder(root):
    stack, prev, node = [], None, root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        node = node.right
    return True

Karmaşıklık

Her iki yöntem de O(n) zaman, O(h) bellek.

Tekrarlayan değerlere izin verilip verilmediğini sorun; tanıma göre < veya <= değişir.