Leetcode 98 Validate Binary Search Tree

Soru

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Örnek 1

Input: root = [2,1,3]
Output: true

Örnek 2

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Çözüm

• Bir binary tree (ikili ağaç) veriliyor, bu ağacın geçerli bir Binary Search Tree (BST) olup olmadığını kontrol edeceğiz.
• BST Nedir?Her bir node (düğüm) için:
• Sol alt ağaçtaki tüm değerler: node.val’den küçük olmalı
• Sağ alt ağaçtaki tüm değerler: node.val’den büyük olmalı
• Bu kural tüm alt ağaçlar için geçerli olmalı, sadece direkt çocuklar için değil.
• inorder Traversal ile BST Kontrolü
• Eğer bir ağaç geçerli bir BST ise, inorder traversal sonucu artan sırada olur.
• Yani:Sol alt ağaç → Kök → Sağ alt ağaç şeklinde gezeriz.
• Her adımda bir önceki düğümün değerini saklarız (prev).
• Eğer şu anki düğümün değeri prev’den küçük veya eşit olursa, kural bozulmuştur → Geçerli BST değildir.
• Neden Inorder Traversal Kullanılır?BST’lerde inorder traversal sonucu sıralı olur.
• Bu yüzden tek bir değişken (prev) ile kontrol etmek mümkündür.
• Fazladan veri yapısı kullanmadan, çok sade bir şekilde kontrol yapılır.

Code

class Solution:
    def isValidBST(self, root):
        self.prev = None  # Önceki düğüm değerini saklamak için
        
        def inorder(node):
            if not node:
                return True
            
            # 1. Sol alt ağacı kontrol et
            if not inorder(node.left):
                return False
            
            # 2. Şu anki düğüm BST kuralını bozuyor mu?
            if self.prev is not None and node.val <= self.prev:
                return False  # Sıra bozuldu: geçerli BST değil
            self.prev = node.val  # Güncel değeri sakla
            
            # 3. Sağ alt ağacı kontrol et
            return inorder(node.right)
        
        return inorder(root)

               

Complexity

• Time complexity (Zaman Karmaşıklığı): O(N) → Her düğüm bir kez ziyaret edilir
• Space complexity (Alan Karmaşıklığı): O(H) → H = ağacın yüksekliği (recursive stack)