5.4: BST Örnek Sorular

1

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

💡 İpucu: Recursive düşünün: Bir node'un yüksekliği = 1 + max(sol_yükseklik, sağ_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

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

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

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

print(f"Yükseklik: {height(root)}")

Çıktı bekleniyor...

2

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)}")

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

def find_min(node):
    while node.left:
        node = node.left
    return node.data

def find_max(node):
    while node.right:
        node = node.right
    return node.data

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

print(f"Min: {find_min(root)}, Max: {find_max(root)}")

Çıktı bekleniyor...

3

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)}")

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

def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if node is None:
        return True
    if node.data <= min_val or node.data >= max_val:
        return False
    return (is_valid_bst(node.left, min_val, node.data) and
            is_valid_bst(node.right, node.data, max_val))

root = Node(50)
root.left = Node(30)
root.right = Node(70)
print(f"Geçerli BST mi? {is_valid_bst(root)}")

Çıktı bekleniyor...

4

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}")

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

def kth_smallest(root, k):
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.data)
            inorder(node.right)
    inorder(root)
    return result[k-1] if k <= len(result) else None

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

print(f"2. en küçük: {kth_smallest(root, 2)}")

Çıktı bekleniyor...

5

Lowest Common Ancestor (LCA)

Orta

BST'de iki node'un en yakın ortak atasını (LCA) bulan fonksiyon yazın.

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

💡 İ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!

👁️ Çö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}")

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

def lca(root, p, q):
    while root:
        if p < root.data and q < root.data:
            root = root.left
        elif p > root.data and q > root.data:
            root = root.right
        else:
            return root.data
    return None

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

print(f"LCA(20, 40) = {lca(root, 20, 40)}")

Çıktı bekleniyor...

🧩 5.4: BST Örnek Sorular

BST'nin Yüksekliğini Bulma

Minimum ve Maksimum Değer

BST Doğrulama

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

Lowest Common Ancestor (LCA)

📚 Ek Pratik Soruları