PricingLoginStart free
DSA Interview Prep · leksjon

K-te minste, intervallsum og BST til sortert array

Utnytt den sorterte in-order-gjennomgangen til å finne det k-te minste elementet i O(k) og summere verdier innenfor et intervall i O(log n + k).

Leksjon 4 av 413 trinn

K-te minste, intervallsum og BST til sortert array er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 4 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Det k-te minste elementet i en BST

Kth Smallest Element in a BST (LeetCode #230) er et klassisk problem som utnytter den sorterte in-order-traverseringen direkte. Siden in-order besøker nodene i stigende rekkefølge, teller vi ganske enkelt nodene under traverseringen og returnerer verdien ved telling k. Tidskompleksiteten er O(h + k), der h er høyden (for å nå noden lengst til venstre), og k er antallet trinn i in-order-gjennomgangen.

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

Det k-te minste: iterativt med stakk

Den iterative varianten bruker mønsteret for in-order-traversering med en eksplisitt stakk. Legg venstre noder på stakken til du når null, og fjern deretter en node fra stakken og øk telleren. Når telleren når k, returneres verdien i den gjeldende noden. Dette unngår Pythons rekursjonsgrense for svært dype trær og har også tidskompleksitet O(h + k) og plasskompleksitet O(h). Intervjuere ber ofte om den iterative varianten etter den rekursive.

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ørste elementet i en BST

Kth Largest bruker omvendt in-order-traversering (right → root → left), som besøker nodene i synkende rekkefølge. Tell k trinn og returner verdien i den gjeldende noden. Dette er symmetrisk med det k-te minste elementet og har tidskompleksitet O(h + k). Alternativt kan du beregne kth_smallest(root, total_count - k + 1) hvis du kjenner størrelsen på treet, men den omvendte in-order-metoden er 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)

Intervallsum i BST

Range Sum of BST (LeetCode #938) ber om summen av alle verdier i [low, high]. Utnytt BST-egenskapen til å beskjære søket: Hvis verdien i den gjeldende noden er mindre enn low, ligger hele det venstre deltreet også under low – hopp over det. Hvis den gjeldende verdien er større enn high, hopper du over det høyre deltreet. Dette beskjærer mange grener og er mer effektivt enn en full in-order-gjennomgang.

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

Tell noder i et intervall

Å telle noder i intervallet [low, high] følger den samme beskjæringslogikken. Et alternativ er å bruke bisect_left/bisect_right på in-order-arrayet – men direkte BST-traversering har kompleksitet O(log n + k), mens konvertering til array først alltid har kompleksitet O(n). Velg direkte traversering med mindre du må besvare mange intervallspørringer. I så fall kan en forberiket BST med deltreantall gi O(log n) per spørring.

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 til sortert array: full algoritme

Å konvertere en BST til et sortert array tar O(n) tid og O(n) plass. Bruk in-order-traversering og legg til hver verdi. Dette er utgangspunktet for flertrinnsproblemer som «slå sammen to BST-er», «finne medianen i en BST» eller «kontrollere om to BST-er har samme in-order-sekvens». Det resulterende arrayet støtter O(1)-tilgang via indeks, binærsøk og topekerteknikker som BST-en ikke kan tilby direkte.

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)

Utvidet BST: Størrelser på deltrær

En utvidet BST lagrer tilleggsinformasjon i hver node, for eksempel størrelsen på deltreet. Med størrelser på deltrær blir det å finne den k-te minste verdien O(log n): I hver node er den gjeldende noden svaret hvis størrelsen på venstre deltre er k-1; hvis størrelsen på venstre deltre er >= k, fortsetter søket rekursivt til venstre; ellers trekkes størrelsen fra, og søket fortsetter til høyre. Dette er datastrukturen bak ordensstatistikktrær som brukes i konkurranseprogrammering.

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

Finn alle verdier i en BST mellom to noder

For å returnere alle verdier som ligger strengt mellom to noder p og q (der p.val < q.val) kombineres in-order-gjennomgang med intervallbeskjæring: Begynn å samle verdier når p.val er passert, og stopp etter q.val. Dette er en generalisering av intervallsum og gir den sorterte sekvensen mellom de to spørringsverdiene på O(h + k)-tid.

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 en BST

Medianen i en BST er den midterste verdien i in-order-gjennomgangen. For n noder ligger medianen på indeksen n // 2 (0-indeksert). Man kan enten samle hele den sorterte arrayen og hente verdien på denne indeksen, eller bruke to gjennomganger: Tell først n noder, og utfør deretter en ny in-order-gjennomgang som stopper ved den n // 2-te noden. Alternativt kan man bruke k-te minste 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ærmeste verdiene til en målverdi

Finn de k verdiene i en BST som ligger nærmest en målverdi. En topeker-tilnærming er å konvertere til en sortert array og bruke et glidende vindu med størrelse k. Alternativt kan man bruke en maks-heap med størrelse k, der avstandene legges inn, og den største avstanden fjernes når størrelsen overstiger k. Løsningen med sortert array bruker O(n) tid og er enkel; heap-løsningen bruker O(n log k), men fungerer i en strømmekontekst.

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]

Utnyttelse av egenskapen for etterfølgere i sortert rekkefølge

Mange BST-problemer kan reduseres til å finne det neste eller forrige elementet i sortert rekkefølge — operasjoner som utføres på O(log n) ved navigering i en BST. Iteratoren vi bygde tidligere gir neste element på amortisert O(1)-tid. Ved å kombinere kunnskap om k-te minste, intervallsum og nærmeste verdi kan man løse de fleste BST-problemer i tekniske intervjuer ved å spørre: «Hvordan forenkler den sorterte rekkefølgen i in-order-gjennomgangen dette?» Dette overordnede mønsteret er kompasset for problemløsing med BST-er.

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

Kontrollspørsmål

Test forståelsen av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen har De lært: k-te minste og største ved hjelp av in-order- og omvendt in-order-gjennomgang på O(h+k)-tid, intervallsum med BST-beskjæring for effektive intervallspørringer, og hvordan en BST konverteres til en sortert array som grunnlag for array-baserte algoritmer. Neste tema er heaper og prioritetskøer.

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs
30
Leksjoner
120
Start læringen gratisSe hele kurset

Ofte stilte spørsmål

Er leksjonen «K-te minste, intervallsum og BST til sortert array» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «K-te minste, intervallsum og BST til sortert array», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «K-te minste, intervallsum og BST til sortert array»?

Utnytt den sorterte in-order-gjennomgangen til å finne det k-te minste elementet i O(k) og summere verdier innenfor et intervall i O(log n + k). Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «K-te minste, intervallsum og BST til sortert array»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

  1. BST-innsetting og -søk
  2. BST-sletting: tre tilfeller
  3. Validering av BST og egenskaper ved in-order
  4. K-te minste, intervallsum og BST til sortert array
← Tilbake til DSA Interview Prep