PricingLoginStart free
DSA Interview Prep · Lektion

K:te minsta, intervallsumma och BST till sorterad array

Utnyttja den sorterade in-order-genomgången för att hitta det k:te minsta elementet i O(k) och summera värden inom ett intervall i O(log n + k).

Lektion 4 av 413 steg

K:te minsta, intervallsumma och BST till sorterad array är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

Det k:te minsta elementet i ett BST

Kth Smallest Element in a BST (LeetCode #230) är ett klassiskt problem som utnyttjar den sorterade inordertraverseringen direkt. Eftersom inordertraverseringen besöker noderna i stigande ordning räknar vi helt enkelt noderna medan vi traverserar och returnerar värdet vid räknare k. Tiden är O(h + k), där h är höjden (för att nå den vänstraste noden) och k är antalet steg i inordergenomgången.

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:te minsta: iterativt med stack

Den iterativa versionen använder det explicita stackmönstret för inordertraversering. Lägg vänsternoder på stacken tills ni når null, ta sedan bort den översta noden och räkna. När räknaren når k returnerar ni den aktuella nodens värde. Detta undviker Pythons rekursionsgräns för mycket djupa träd och har på samma sätt O(h + k) tidskomplexitet och O(h) rymdkomplexitet. Intervjuare frågar ofta efter den iterativa versionen efter den rekursiva.

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

Det k:te största elementet i ett BST

Kth Largest använder omvänd inordertraversering (höger → rot → vänster), som besöker noderna i avtagande ordning. Räkna k steg och returnera den aktuella nodens värde. Detta är symmetriskt mot att hitta det k:te minsta elementet och körs på O(h + k) tid. Alternativt kan ni beräkna kth_smallest(root, total_count - k + 1) om ni känner till trädets storlek, men den omvända inordermetoden är mer elegant.

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)

Intervallsumma i BST

Range Sum of BST (LeetCode #938) frågar efter summan av alla värden i [low, high]. Utnyttja BST-egenskapen för att beskära sökningen: om den aktuella nodens värde är mindre än low ligger hela det vänstra delträdet också under low – hoppa över det. Om det aktuella värdet är större än high hoppar ni över det högra delträdet. Detta beskär många grenar och är effektivare än en fullständig inordergenomgång.

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

Räkna noder inom ett intervall

Att räkna noder inom intervallet [low, high] följer samma beskärningslogik. Ett alternativ är att använda bisect_left/bisect_right på inorderarrayen – men en direkt BST-genomgång tar O(log n + k), medan en föregående konvertering till array alltid tar O(n). Välj direkt genomgång om ni inte behöver besvara många intervallfrågor. I så fall kan ett utökat BST med antal noder i delträd ge O(log n) per fråga.

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 till sorterad array (fullständig algoritm)

Att konvertera ett BST till en sorterad array tar O(n) tid och O(n) utrymme. Använd inordertraversering och lägg till varje värde. Detta är utgångspunkten för problem med flera steg: "slå ihop två BST:er", "hitta medianen i ett BST" eller "kontrollera om två BST:n har samma inordersekvens". Den resulterande arrayen stöder åtkomst via index på O(1), binärsökning och tvåpekartekniker som BST:t inte kan erbjuda direkt.

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)

Augmenterat BST: delträdens storlek

Ett augmenterat BST lagrar ytterligare information i varje nod, till exempel storleken på dess delträd. Med delträdens storlek kan det k:te minsta elementet hittas på O(log n): vid varje nod gäller att om storleken på vänster delträd är k-1 är den aktuella noden svaret; om storleken på vänster delträd är >= k fortsätter sökningen rekursivt åt vänster; annars subtraheras storleken och sökningen fortsätter åt höger. Detta är datastrukturen bakom ordningsstatistikträd som används i tävlingsprogrammering.

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')

Hitta alla värden i ett BST mellan två noder

För att returnera alla värden som ligger strikt mellan två noder p och q (där p.val < q.val) kombinerar ni inordertraversering med intervallbeskärning: börja samla in värden när ni passerar p.val och sluta efter q.val. Detta är en generalisering av intervallsumma och ger den sorterade följden mellan de två frågevärdena på O(h + k).

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]

Medianen i ett BST

Medianen i ett BST är det mittersta värdet i inordertraverseringen. För n noder finns medianen på index n // 2 (0-indexerat). Antingen samlar ni hela den sorterade arrayen och hämtar värdet på det indexet, eller så använder ni två genomgångar: räkna först n noder och gör sedan en andra inordertraversering som stannar vid noden på plats n // 2. Alternativt kan ni använda det k:te minsta elementet med k = n // 2 + 1.

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])

De k närmaste värdena till målet

Hitta de k värden i ett BST som ligger närmast ett målvärde. En tvåpekarmetod är att omvandla trädet till en sorterad array och använda ett glidande fönster med storlek k. Alternativt kan ni använda en max-heap med storlek k, där ni lägger in avstånden och tar bort det största när storleken överstiger k. Metoden med sorterad array tar O(n) tid och är enkel; heap-metoden tar O(n log k), men fungerar i ett strömningssammanhang.

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]

Utnyttja egenskapen hos efterföljare

Många BST-problem kan reduceras till att hitta nästa eller föregående element i sorterad ordning — operationer som tar O(log n) med BST-navigering. Iteratören vi byggde tidigare ger amorterad O(1) för next. Genom att kombinera kunskaper om det k:te minsta elementet, intervallsumma och närmaste värde kan ni lösa de flesta BST-problem i tekniska intervjuer genom att fråga: ”Hur förenklar den sorterade ordningen i inordertraverseringen detta?” Detta metamönster fungerar som en kompass för problemlösning med BST.

# 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')

Snabbkontroll

Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.

Besvara frågan i den interaktiva lektionen

Sammanfattning av lektionen

I den här lektionen lärde ni er: det k:te minsta och största elementet med inorder- och omvänd inordertraversering på O(h+k), intervallsumma med BST-beskärning för effektiva intervallfrågor samt att omvandla ett BST till en sorterad array som grund för arraybaserade algoritmer. Nästa steg är heaps och prioritetsköer.

Gratis att börja

Lär dig Python med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser
30
Lektioner
120
Börja lära dig gratisVisa hela kursen

Vanliga frågor

Är lektionen ”K:te minsta, intervallsumma och BST till sorterad array” gratis?

Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”K:te minsta, intervallsumma och BST till sorterad array”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.

Vad lär jag mig i ”K:te minsta, intervallsumma och BST till sorterad array”?

Utnyttja den sorterade in-order-genomgången för att hitta det k:te minsta elementet i O(k) och summera värden inom ett intervall i O(log n + k). Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?

Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.

Hur lång tid tar lektionen ”K:te minsta, intervallsumma och BST till sorterad array”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?

Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

  1. Infogning och sökning i BST
  2. Ta bort från BST: tre fall
  3. Verifiera BST och in-order-egenskaper
  4. K:te minsta, intervallsumma och BST till sorterad array
← Tillbaka till DSA Interview Prep