🧩 5.4: BST Örnek Sorular

Pratik Yaparak Öğrenin

📋 Bu Bölümde Neler Öğreneceksiniz?

Bu sayfada BST üzerinde sıkça sorulan klasik mülakatsorularını ve algoritma problemlerini çözeceğiz. Her problem için:

🎯
Problem Tanımı
Net ve anlaşılır
💡
Çözüm Stratejisi
Nasıl düşünmeli?
🖥️
Çalıştırılabilir Kod
Python ile test et
⚡
Zaman/Alan Analizi
Performans detayları

🎮 İnteraktif BST Test Aracı

Aşağıdaki problemi çözmeden önce kendi BST'nizi oluşturun ve test edin!

📊 Ağaç Bilgileri

Düğüm Sayısı: 0
Yükseklik: -1
Minimum: -
Maksimum: -
Inorder: []

BST'nin Yüksekliğini Bulma

Kolay

Bir BST'nin yüksekliğini (height) bulan fonksiyon yazın. Yükseklik, kökten en derin yaprağa olan kenar sayısıdır.

Örnek: Ağaç [50, 30, 70, 20, 40] → Yükseklik: 2

🧠 Düşünce Süreci

Base Case: Boş düğüm (None) için yükseklik = -1
Recursive Case: Her düğüm için:
- Sol alt ağacın yüksekliğini bul
- Sağ alt ağacın yüksekliğini bul
- Daha büyük olanı al + 1 (kendisi için)
Formül: height(node) = 1 + max(height(left), height(right))

       50        ← Seviye 0 (Kök)
      /  \
    30    70     ← Seviye 1
   /  \
  20   40        ← Seviye 2 (Yaprak)

Yükseklik = En derin seviye = 2

💡 İpucu: Recursive düşünün: Bir node'un yüksekliği = 1 + max(sol_yükseklik, sağ_yükseklik)

⚡ Karmaşıklık Analizi

Zaman: O(n) - Her düğümü bir kez ziyaret

Alan: O(h) - Recursion stack (h = yükseklik)

👁️ Çözümü Göster/Gizle

Python Çözümü

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def height(node):
    """
    BST yüksekliğini bul - O(n)
    Her node'u bir kez ziyaret etmemiz gerekir
    """
    # Base case: Boş node
    if node is None:
        return -1  # Boş ağacın yüksekliği -1

    # Recursive: Sol ve sağ alt ağaçların yüksekliği
    left_height = height(node.left)
    right_height = height(node.right)

    # Maksimum + 1 (bu node için)
    return 1 + max(left_height, right_height)

# Test
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)

print("🌳 Ağaç yapısı:")
print("       50")
print("      /  \\")
print("    30    70")
print("   /  \\")
print("  20   40")
print()
print(f"Yükseklik: {height(root)}")  # 2

# Daha derin ağaç test et
root.left.left.left = Node(10)
print(f"\n10 eklendi → Yeni yükseklik: {height(root)}")  # 3

Çıktı bekleniyor...

Minimum ve Maksimum Değer

Kolay

BST'deki minimum ve maksimum değerleri bulan fonksiyonlar yazın.

Örnek: Ağaç [50, 30, 70, 20, 40, 60, 80] → Min: 20, Max: 80

💡 İpucu: BST özelliği: En küçük değer en soldaki node, en büyük değer en sağdaki node!

👁️ Çözümü Göster/Gizle

Python Çözümü

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def find_min(node):
    """
    BST'deki minimum değer - O(h)
    Her zaman sola git!
    """
    if node is None:
        return None

    current = node
    while current.left:
        current = current.left

    return current.data

def find_max(node):
    """
    BST'deki maksimum değer - O(h)
    Her zaman sağa git!
    """
    if node is None:
        return None

    current = node
    while current.right:
        current = current.right

    return current.data

# Recursive versiyonlar
def find_min_recursive(node):
    if node is None:
        return None
    if node.left is None:
        return node.data
    return find_min_recursive(node.left)

def find_max_recursive(node):
    if node is None:
        return None
    if node.right is None:
        return node.data
    return find_max_recursive(node.right)

# Test
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

print("🌳 Ağaç: [50, 30, 70, 20, 40, 60, 80]")
print()
print(f"Minimum (iteratif): {find_min(root)}")
print(f"Maksimum (iteratif): {find_max(root)}")
print()
print(f"Minimum (recursive): {find_min_recursive(root)}")
print(f"Maksimum (recursive): {find_max_recursive(root)}")

Çıktı bekleniyor...

BST Doğrulama

Orta

Verilen bir binary tree'nin geçerli bir BST olup olmadığını kontrol eden fonksiyon yazın.

Örnek 1: [50, 30, 70] → True (Geçerli BST)
Örnek 2: [50, 70, 30] (sol çocuk > kök) → False

💡 İpucu: Inorder traversal kullanın! BST ise inorder çıktı sıralı olmalı.

👁️ Çözümü Göster/Gizle

Python Çözümü

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def is_valid_bst_inorder(root):
    """
    Yöntem 1: Inorder traversal ile kontrol
    BST ise → inorder çıktı kesinlikle sıralı!
    """
    result = []

    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.data)
            inorder(node.right)

    inorder(root)

    # Sıralı mı kontrol et
    for i in range(1, len(result)):
        if result[i] <= result[i-1]:
            return False
    return True

def is_valid_bst_bounds(node, min_val=float('-inf'), max_val=float('inf')):
    """
    Yöntem 2: Min/Max sınırları ile kontrol
    Her node belirli bir aralıkta olmalı!
    """
    if node is None:
        return True

    # Bu node sınırlar içinde mi?
    if node.data <= min_val or node.data >= max_val:
        return False

    # Sol: max sınır = bu node'un değeri
    # Sağ: min sınır = bu node'un değeri
    return (is_valid_bst_bounds(node.left, min_val, node.data) and
            is_valid_bst_bounds(node.right, node.data, max_val))

# Test 1: Geçerli BST
print("=" * 50)
print("Test 1: Geçerli BST")
print("=" * 50)
root1 = Node(50)
root1.left = Node(30)
root1.right = Node(70)
root1.left.left = Node(20)
root1.left.right = Node(40)

print(f"Inorder yöntemi: {is_valid_bst_inorder(root1)}")
print(f"Bounds yöntemi: {is_valid_bst_bounds(root1)}")

# Test 2: Geçersiz BST (sol çocuk > kök)
print("\n" + "=" * 50)
print("Test 2: Geçersiz BST (sol > kök)")
print("=" * 50)
root2 = Node(50)
root2.left = Node(60)  # YANLIŞ! 60 > 50
root2.right = Node(70)

print(f"Inorder yöntemi: {is_valid_bst_inorder(root2)}")
print(f"Bounds yöntemi: {is_valid_bst_bounds(root2)}")

# Test 3: Karmaşık geçersiz BST
print("\n" + "=" * 50)
print("Test 3: Gizli hata (sol alt ağaçta büyük değer)")
print("=" * 50)
#       50
#      /  \
#    30    70
#   /  \
#  20  60  ← 60 > 50, BST kuralı ihlali!
root3 = Node(50)
root3.left = Node(30)
root3.right = Node(70)
root3.left.left = Node(20)
root3.left.right = Node(60)  # YANLIŞ!

print(f"Inorder yöntemi: {is_valid_bst_inorder(root3)}")
print(f"Bounds yöntemi: {is_valid_bst_bounds(root3)}")

Çıktı bekleniyor...

k'ıncı En Küçük Eleman

Orta

BST'deki k'ıncı en küçük elemanı bulan fonksiyon yazın.

Örnek: Ağaç [50, 30, 70, 20, 40], k=3 → 40 (20, 30, 40)

💡 İpucu: Inorder traversal sıralı çıktı verir. k'ıncı eleman = inorder[k-1]

👁️ Çözümü Göster/Gizle

Python Çözümü

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def kth_smallest(root, k):
    """
    k'ıncı en küçük eleman - O(n)
    Inorder traversal ile
    """
    result = []

    def inorder(node):
        if node and len(result) < k:  # Optimizasyon: k eleman yeterli
            inorder(node.left)
            result.append(node.data)
            inorder(node.right)

    inorder(root)

    if k <= len(result):
        return result[k-1]
    return None

def kth_smallest_iterative(root, k):
    """
    k'ıncı en küçük eleman - O(h + k)
    Stack ile iteratif inorder - daha verimli!
    """
    stack = []
    current = root
    count = 0

    while stack or current:
        # En sola git
        while current:
            stack.append(current)
            current = current.left

        # Backtrack
        current = stack.pop()
        count += 1

        if count == k:
            return current.data

        current = current.right

    return None

# Test
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

print("🌳 Ağaç: [50, 30, 70, 20, 40, 60, 80]")
print("📋 Sıralı: [20, 30, 40, 50, 60, 70, 80]")
print()

for k in [1, 3, 5, 7]:
    result = kth_smallest(root, k)
    print(f"{k}. en küçük: {result}")

Çıktı bekleniyor...

Lowest Common Ancestor (LCA)

Orta

BST'de iki node'un en yakın ortak atasını (LCA) bulan fonksiyon yazın. LCA, her iki düğümün de atasıolduğu en düşük seviyedeki düğümdür.

Örnek: Ağaç [50, 30, 70, 20, 40], nodes: 20 ve 40 → LCA: 30

🧠 LCA Nedir ve Neden Önemli?

LCA (Lowest Common Ancestor), iki düğümün ortak atasıdır. Örneğin:

Soy ağacı: İki kuzenin ortak büyük ebeveynini bulma
Dosya sistemi: İki dosyanın ortak klasörünü bulma
Network: İki node arasındaki routing noktası

📊 LCA Mantığı (BST İçin)

⬅️

İkisi de Solda
p < kök AND q < kök
→ Sol çocuğa git

➡️

İkisi de Sağda
p > kök AND q > kök
→ Sağ çocuğa git

✅

Ayrıldılar!
p ve q farklı yönlerde
→ Bu düğüm LCA!

🎮 İnteraktif LCA Simülasyonu

1. Düğüm (p):

2. Düğüm (q):

💡 İpucu: BST özelliği: İki değer de kökten küçükse sola, büyükse sağa git. Aksi halde kök LCA'dır!

⚡ Karmaşıklık Analizi

Zaman: O(h) - Sadece bir yol izlenir

Alan: O(1) iteratif, O(h) recursive

👁️ Çözümü Göster/Gizle

Python Çözümü

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def lca(root, p, q):
    """
    Lowest Common Ancestor - O(h)
    BST özelliğini kullan!
    """
    current = root

    while current:
        # İkisi de solda
        if p < current.data and q < current.data:
            current = current.left
        # İkisi de sağda
        elif p > current.data and q > current.data:
            current = current.right
        # Biri solda, biri sağda (veya biri current)
        else:
            return current.data

    return None

def lca_recursive(root, p, q):
    """Recursive versiyon"""
    if root is None:
        return None

    if p < root.data and q < root.data:
        return lca_recursive(root.left, p, q)
    elif p > root.data and q > root.data:
        return lca_recursive(root.right, p, q)
    else:
        return root.data

# Test
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

print("🌳 Ağaç yapısı:")
print("       50")
print("      /  \\")
print("    30    70")
print("   /  \\  /  \\")
print("  20  40 60  80")
print()

test_cases = [(20, 40), (20, 80), (60, 80), (30, 70)]
for p, q in test_cases:
    result = lca(root, p, q)
    print(f"LCA({p}, {q}) = {result}")

Çıktı bekleniyor...

📚 Ek Pratik Soruları (Kendiniz Çözün!)

Aşağıdaki sorularla pratik yapmayı deneyin. Her biri farklı bir BST becerisini test eder:

🔄 BST'yi Aynalama (Mirror)

Tüm sol ve sağ çocukları yer değiştirin. Sonuç: Inorder ters sıralı olacak!

Kolay

📏 BST Dengeli mi?

Her düğüm için sol ve sağ alt ağaç yükseklikleri en fazla 1 fark etmeli.

Orta

🔢 Belirli Aralıktaki Değerler

Verilen [low, high] aralığındaki tüm değerleri yazdırın. BST özelliğini kullanın!

Orta

🔗 Sıralı Diziden Dengeli BST

Sıralı bir diziyi O(n) sürede dengeli BST'ye dönüştürün. İpucu: Ortadan başlayın!

Zor

🌿 Tüm Yaprakları Yazdırma

Çocuğu olmayan tüm düğümleri (yaprakları) bulun ve yazdırın.

Kolay

🎯 Inorder Successor

Bir düğümün inorder sırada bir sonraki düğümünü bulun. Silme işleminde kullanılır!

Orta

💡 Çözüm Stratejisi

Her soruda önce base case ve recursive case'i belirleyin. BST özelliğini (sol < kök < sağ) her zaman aklınızda tutun!