İkili arama ağacını doğrulama

Problem

Bir ikili ağacın kökü veriliyor. Bu ağacın geçerli bir ikili arama ağacı (BST) olup olmadığını söyle. Geçerli BST'de her düğüm için sol alt ağaçtaki bütün değerler düğümden kesin küçük, sağ alt ağaçtaki bütün değerler kesin büyüktür ve bu kural her alt ağaç için tekrar geçerlidir.

        20
       /  \
     10    30
    /  \
   5    25

Çıktı: false

Her düğüm kendi çocuklarıyla tek tek uyumlu görünüyor (10 < 25 sağ çocuk, 5 < 10 sol çocuk), ama 25 kökün sol alt ağacında ve 20'den büyük. Kural tüm alt ağaç için geçerli.

Girdi: [20, 10, 30, 5, 15, 25, 40]
Çıktı: true

Netleştirme soruları

• Eşit değerler nereye gider? (LeetCode'da hiçbir yere: eşitlik BST'yi geçersiz yapar. Bazı tanımlarda eşitler sola ya da sağa izinlidir; sormak gerekir.)
• Değer aralığı ne? Integer.MIN_VALUE ve Integer.MAX_VALUE düğüm değeri olabilir mi? (Evet; bu, sınır olarak int kullanmayı bozar.)
• Boş ağaç geçerli mi? (Evet.)
• Ağaç ne kadar derin olabilir?

İpuçları

Yaklaşım

Yanlış ama çekici çözüm: Her düğümde left.val < node.val < right.val kontrolü. Yukarıdaki ilk örneği yanlışlıkla true kabul eder. Bu sorunun neredeyse tek amacı bu tuzağı görmektir.

Kaba ama doğru çözüm: Her düğüm için sol alt ağacın maksimumunu ve sağ alt ağacın minimumunu ayrı ayrı hesaplamak. Her düğümde alt ağacı yeniden dolaştığı için O(n·h), zincirde O(n²). (Max/min'i alttan yukarı tek geçişte taşıyan versiyonu O(n)'dir ve geçerli bir alternatiftir.)

Aralık taşıyan DFS (optimal): Kök için aralık (-∞, +∞). Bir düğümden sola inerken üst sınır düğümün değeri olur, sağa inerken alt sınır. Her düğüm kendi açık aralığında olmalıdır. Bu, "atalarının koyduğu bütün kısıtları" iki sayıya sıkıştırır: en sıkı alt sınır ve en sıkı üst sınır.

Sınır tipi: Düğüm değerleri int'in tamamını kapsayabildiği için sınırı Integer.MIN_VALUE ile başlatmak, değeri tam Integer.MIN_VALUE olan geçerli bir düğümü reddeder. Çözüm: sınırları long tutmak ya da Integer ile null'ı "sınırsız" anlamında kullanmak.

Inorder alternatifi: İteratif inorder (açık stack ile) ve prev değişkeni. Stack taşmasını önler ve ilk ihlalde erken döner.

Java çözümü

public final class ValidateBst {

    static final class TreeNode {
        final int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
    }

    public boolean isValidBST(TreeNode root) {
        // long sınırlar: düğüm değeri Integer.MIN_VALUE/MAX_VALUE olabilir
        return isWithin(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /** Alt ağaçtaki her değer (low, high) açık aralığında olmalı. */
    private boolean isWithin(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;     // eşitlik de ihlal: BST kesin küçük/büyük
        return isWithin(node.left, low, node.val)                  // sol: üst sınır daralır
                && isWithin(node.right, node.val, high);           // sağ: alt sınır daralır
    }
}

Karmaşıklık

• Zaman: O(n); her düğüm bir kez ziyaret edilir ve ilk ihlalde && kısa devresiyle durur.
• Bellek: O(h) özyineleme stack'i; dengeli ağaçta O(log n), zincirde O(n).

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• Geçerli dengeli ağaç: true.
• Torunun köke göre ihlali ([20, 10, 30, 5, 25]): false. Yerel kontrolün geçtiği, aralık kontrolünün yakaladığı test.
• Sağ alt ağaçta kökten küçük değer ([20, 10, 30, null, null, 15, 40]): false.
• Tekrar eden değerler ([2, 2, 2], [5, null, 5]): false.
• Boş ağaç: true.
• Tek düğüm Integer.MIN_VALUE ve tek düğüm Integer.MAX_VALUE: true. Sınırları int tutan çözüm bu iki testte false döner.
• [MIN, null, MAX]: true; [MAX, MAX]: false.
• 2.000 rastgele küçük ağaçta sonuç, "inorder diziyi çıkar, kesin artan mı bak" referansıyla karşılaştırıldı.

Mülakatçı için

Adayın ilk refleksi yerel kontrolse, hemen düzeltme. Örneği "kodunu şu ağaçla dry run eder misin: 20, sol 10, 10'un sağı 25" diye ver. Hatasını kendi bulması güçlü bir öğrenme ve iletişim sinyalidir. Aralık fikrine ulaştıktan sonra Integer.MIN_VALUE testini sor; Java'da sınır tiplerini düşünen aday ayrışır.

İpucu zamanlaması: Yerel kontrol hatası fark edildikten sonra 3 dakika içinde ilerleme yoksa ikinci ipucunu (aralık) ver. Inorder ipucunu, aralık çözümü bittikten sonra "başka bir yolu var mı?" sorusuyla birlikte kullan.

Takip sorusu 1: Eşit değerlerin sol alt ağaçta olmasına izin ver. Beklenen: sol tarafta kontrol val <= high, sağ tarafta val > low; yani aralık sol için yarı kapalı olur. Inorder versiyonunda "artan" yerine "azalmayan" kontrolü tek başına yetmez, çünkü eşitin sağda durduğu ağacı da kabul eder; aralık versiyonu daha güvenlidir.

Takip sorusu 2: BST'de iki düğümün değerleri yanlışlıkla yer değiştirmiş; ağacı yapısını değiştirmeden düzelt. Beklenen: inorder dizide bir ya da iki "düşüş" noktası bulmak; ilk düşüşün büyük elemanı ile son düşüşün küçük elemanını takas etmek (LeetCode 99). O(1) ek bellek istenirse Morris traversal.

Takip sorusu 3: Bu doğrulamayı, bir REST endpoint'ine gelen ağaç yapılı JSON (kategori ağacı gibi) için yapacaksın. Ne eklersin? Beklenen: maksimum derinlik ve düğüm sayısı limiti (kötü niyetli derin girdiye karşı), iteratif dolaşım, hatalı düğümün yolunu döndüren anlamlı bir hata mesajı.

Benzer problemler

• Recover Binary Search Tree (LeetCode 99)
• Kth Smallest Element in a BST (LeetCode 230)
• Lowest Common Ancestor of a Binary Search Tree (LeetCode 235)
• Inorder Successor in BST (LeetCode 285)
• Convert Sorted Array to Binary Search Tree (LeetCode 108)