DSA Interview Prep · Ders

K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye

Q: “K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye” dersi ücretsiz mi?

Evet — “K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Q: DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.

Q: “K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Sıralı orta sıralı dolaşımdan yararlanarak O(k) sürede k’inci en küçük öğeyi bulun ve O(log n + k) sürede bir aralıktaki değerleri toplayın.

K’inci En Küçük, Aralık Toplamı ve BST’den Sıralı Diziye, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

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

BST'de K'ıncı En Küçük Eleman (LeetCode #230), sıralı dolaşımın sıralı olmasından doğrudan yararlanan klasik bir problemdir. Sıralı dolaşım düğümleri artan düzende ziyaret ettiğinden, dolaşırken düğümleri sayar ve sayı k'ye ulaştığında değeri döndürürüz. Zaman karmaşıklığı O(h + k)'dir; burada h, en soldaki düğüme ulaşmak için gereken ağaç yüksekliği, k ise sıralı dolaşımdaki adım sayısıdır.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1))  # 1
print(kth_smallest(root, 2))  # 2

K'ıncı En Küçük: Yığınla İteratif Çözüm

İteratif sürüm, açıkça kullanılan yığınla sıralı dolaşım kalıbını uygular. Boş olana kadar sol düğümleri yığına itin, ardından düğümü çıkarıp sayın. Sayaç k'ye ulaştığında mevcut düğümün değerini döndürün. Bu yaklaşım, çok derin ağaçlarda Python dilinin özyineleme sınırından kaçınır; ayrıca O(h + k) zaman ve O(h) alan kullanır. Mülakat yapanlar, özyinelemeli sürümün ardından genellikle iteratif sürümü de ister.

def kth_smallest_iterative(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:             # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()      # process node
        count += 1
        if count == k:
            return curr.val
        curr = curr.right       # move to right subtree
    return -1  # k out of range

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3))  # 3

BST'de K'ıncı En Büyük Eleman

K'ıncı En Büyük, düğümleri azalan düzende ziyaret eden ters sıralı dolaşımı (sağ → kök → sol) kullanır. k adımı sayın ve mevcut düğümün değerini döndürün. Bu, k'ıncı en küçük işlemin simetriğidir ve O(h + k) zamanda çalışır. Alternatif olarak, ağaç boyutunu biliyorsanız kth_smallest(root, total_count - k + 1) hesaplayabilirsiniz; ancak ters sıralı yaklaşım daha zariftir.

def kth_largest(root, k):
    count = [0]
    result = [None]

    def reverse_inorder(node):
        if not node or result[0] is not None:
            return
        reverse_inorder(node.right)   # visit LARGER values first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)

    reverse_inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1))  # 4 (largest)
print(kth_largest(root, 2))  # 3 (2nd largest)

BST'nin Aralık Toplamı

BST'nin Aralık Toplamı (LeetCode #938), [low, high] aralığındaki tüm değerlerin toplamını ister. Dalları budamak için BST özelliğinden yararlanın: mevcut düğümün değeri low'dan küçükse sol alt ağacın tamamı da low'un altındadır; bu alt ağacı atlayın. Mevcut değer high'dan büyükse sağ alt ağacı atlayın. Bu yaklaşım birçok dalı budar ve tam bir sıralı taramadan daha verimlidir.

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree might have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:   # right subtree might have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7+10+15 = 32

Aralıktaki Düğümleri Sayma

[low, high] aralığındaki düğümleri saymak da aynı budama mantığını izler. Alternatif olarak sıralı dizi üzerinde bisect_left/sağa bölme kullanılabilir; ancak doğrudan BST dolaşımı O(log n + k) zamanda çalışırken önce diziye dönüştürmek her zaman O(n) zaman alır. Çok sayıda aralık sorgusunu yanıtlamanız gerekmiyorsa doğrudan dolaşımı seçin; böyle bir durumda alt ağaç sayılarıyla zenginleştirilmiş bir BST oluşturmak sorgu başına O(log n) süre sağlar.

def count_range(root, low, high):
    if not root:
        return 0
    count = 0
    if low <= root.val <= high:
        count += 1
    if root.val > low:
        count += count_range(root.left, low, high)
    if root.val < high:
        count += count_range(root.right, low, high)
    return count

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15))  # 7, 10, 15 = 3

BST'den Sıralı Diziye (Tam Algoritma)

Bir BST'yi sıralı diziye dönüştürmek O(n) zaman ve O(n) alan gerektirir. Sıralı dolaşımı kullanın ve her değeri ekleyin. Bu, çok aşamalı problemlerin başlangıç noktasıdır: “iki BST'yi birleştirme”, “BST'nin medyanını bulma” veya “iki BST'nin aynı sıralı dolaşım dizisine sahip olup olmadığını kontrol etme”. Ortaya çıkan dizi, BST'nin doğrudan sağlayamadığı O(1) dizin erişimini, ikili aramayı ve iki gösterici tekniklerini destekler.

def bst_to_sorted(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root))  # [1, 3, 4, 5, 6, 8, 9]

# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6))   # 4 (index of 6)

Genişletilmiş BST: Alt Ağaç Boyutları

Bir genişletilmiş BST, her düğümde alt ağacının boyutu gibi ek bilgiler saklar. Alt ağaç boyutları sayesinde k'ıncı en küçük değer O(log n) sürede bulunabilir: her düğümde, sol alt ağacın boyutu k-1 ise mevcut düğüm yanıttır; sol alt ağacın boyutu k'den büyük veya eşitse sol alt ağaçta özyinelemeli arama yapılır; aksi hâlde k'dan sol alt ağaç boyutu çıkarılır ve sağ alt ağaçta arama yapılır. Bu, yarışmalı programlamada kullanılan sıra istatistiği ağaçlarının temelindeki veri yapısıdır.

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # subtree size

def get_size(node):
    return node.size if node else 0

def update_size(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def kth_smallest_aug(root, k):
    left_size = get_size(root.left)
    if k == left_size + 1:
        return root.val      # current node is kth
    elif k <= left_size:
        return kth_smallest_aug(root.left, k)
    else:
        return kth_smallest_aug(root.right, k - left_size - 1)

print('Augmented BST: O(log n) kth smallest with subtree sizes')

BST'de İki Düğüm Arasındaki Tüm Değerleri Bulma

p ve q düğümleri arasında (p.val < q.val olacak şekilde) kalan tüm değerleri döndürmek için, sıralı dolaşmayı aralık budamasıyla birleştirin: p.val'i geçtikten sonra değerleri toplamaya başlayın ve q.val'den sonra durun. Bu, aralık toplamının genelleştirilmiş hâlidir ve iki sorgu değeri arasındaki sıralı diziyi O(h + k) time maliyetiyle verir.

def values_between(root, low, high):
    result = []
    def inorder(node):
        if not node:
            return
        if node.val > low:    # might be values > low on left
            inorder(node.left)
        if low < node.val < high:  # strictly between
            result.append(node.val)
        if node.val < high:   # might be values < high on right
            inorder(node.right)
    inorder(root)
    return result

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15))  # [7, 10, 12]

BST'nin Medyanı

Bir BST'nin medyanı, sıralı dolaşmadaki ortanca değerdir. n düğüm için medyan, n // 2 indeksindedir (0'dan başlayan indeksleme). Ya sıralanmış dizinin tamamını toplayıp indeksleyin ya da iki geçiş kullanın: önce n düğümün sayısını bulun, ardından ikinci bir sıralı dolaşmada n // 2. düğümde durun. Alternatif olarak k = n // 2 + 1 alarak k'ıncı en küçük değeri kullanabilirsiniz.

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def median_of_bst(root):
    n = count_nodes(root)
    if n == 0:
        return None
    k = n // 2 + 1  # (n+1)/2-th element for odd, n/2+1-th for even
    return kth_smallest(root, k)

def kth_smallest(root, k):
    count = [0]; result = [None]
    def inorder(node):
        if not node or result[0] is not None: return
        inorder(node.left)
        count[0] += 1
        if count[0] == k: result[0] = node.val; return
        inorder(node.right)
    inorder(root); return result[0]

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root))  # 4 (middle of [1,3,4,5,8])

Hedefe En Yakın K Değer

Bir BST'de hedefe en yakın k değeri bulun. İki işaretçili yaklaşım: sıralı diziye dönüştürün ve k boyutunda kayan bir pencere kullanın. Alternatif olarak, k boyutunda bir maksimum yığınında uzaklıkları push edin ve boyut k'yi aştığında pop edin. Sıralı dizi yaklaşımı O(n) time maliyetine sahiptir ve basittir; yığın yaklaşımı O(n log k) maliyetindedir ancak veri akışı bağlamında çalışır.

import heapq

def closest_k_values(root, target, k):
    # Collect sorted values
    arr = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)

    # Two-pointer sliding window of size k
    left, right = 0, k - 1
    while right < len(arr) - 1:
        if abs(arr[left] - target) <= abs(arr[right + 1] - target):
            break  # left is closer, don't advance
        left += 1
        right += 1
    return arr[left:right + 1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2))  # [3, 4]

Ardıl Sıralama Özelliğinden Yararlanma

Birçok BST problemi, sıralı düzende bir sonraki veya önceki öğeyi bulmaya indirgenir; BST üzerinde gezinmeyle bu işlemler O(log n) sürede gerçekleştirilir. Daha önce oluşturduğumuz yineleyici, bir sonraki öğeyi amortismanlı O(1) maliyetle verir. k'ıncı en küçük değer, aralık toplamı ve en yakın değer hakkındaki bilgileri birleştirerek çoğu BST mülakat problemini şu soruyu sorarak çözebilirsiniz: 'Sıralı dolaşmanın sıralı düzeni bunu nasıl basitleştiriyor?' Bu üst örüntü, BST problem çözme pusulanızdır.

# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?

# Quick reference:
# kth smallest  -> in-order, stop at kth node
# kth largest   -> reverse in-order, stop at kth node
# range sum     -> in-order + BST pruning
# closest value -> walk toward target, track best
# median        -> kth with k = n//2+1
# sorted array  -> full in-order
# validate      -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')

Hızlı Kontrol

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: O(h+k) maliyetle sıralı ve ters sıralı dolaşma kullanarak k'ıncı en küçük ve en büyük değerleri bulmayı, verimli aralık sorguları için BST budamasıyla aralık toplamını hesaplamayı ve dizi tabanlı algoritmaların temeli olarak bir BST'yi sıralı diziye dönüştürmeyi. Sırada yığınları ve öncelik kuyruklarını inceleyeceğiz.

Sıkça Sorulan Sorular