K-de kleinste, rangesom en BST naar gesorteerde array
Benut de gesorteerde in-order traversal om het k-de kleinste element te vinden in O(k) en waarden binnen een bereik op te tellen in O(log n + k).
K-de kleinste, rangesom en BST naar gesorteerde array is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 4 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Het k-de kleinste element in een BST
Het k-de kleinste element in een BST (LeetCode #230) is een klassiek probleem dat direct gebruikmaakt van de gesorteerde in-orderdoorloop. Omdat de in-orderdoorloop knopen in oplopende volgorde bezoekt, tellen we eenvoudig de knopen tijdens de doorloop en geven we de waarde terug wanneer teller k bereikt. De tijd is O(h + k), waarbij h de hoogte is (om de meest linkse knoop te bereiken) en k het aantal stappen in de in-orderdoorloop is.
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)) # 2K-de kleinste: iteratief met een stapel
De iteratieve versie gebruikt het patroon van de in-orderdoorloop met een expliciete stapel. Plaats linkse knopen op de stapel tot null, haal daarna een knoop van de stapel en verhoog de teller. Geef de waarde van de huidige knoop terug zodra de teller k bereikt. Hiermee vermijd je de recursielimiet van Python bij zeer diepe bomen. De aanpak kost eveneens O(h + k) tijd en O(h) ruimte. Na de recursieve versie vragen gesprekvoerders vaak ook om de iteratieve versie.
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)) # 3Het k-de grootste element in een BST
Het k-de grootste element gebruikt een omgekeerde in-orderdoorloop (rechts → wortel → links), waarbij knopen in aflopende volgorde worden bezocht. Tel k stappen en geef de waarde van de huidige knoop terug. Dit is het spiegelbeeld van het k-de kleinste element en kost O(h + k) tijd. Je kunt ook kth_smallest(root, total_count - k + 1) berekenen als je de omvang van de boom kent, maar de omgekeerde in-orderaanpak is eleganter.
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)Som van een bereik in een BST
Som van een bereik in een BST (LeetCode #938) vraagt om de som van alle waarden in [low, high]. Benut de BST-eigenschap om deelbomen over te slaan: als de waarde van de huidige knoop kleiner is dan low, ligt de volledige linkerdeelboom ook onder low — sla die over. Als de huidige waarde groter is dan high, sla je de rechterdeelboom over. Hierdoor worden veel takken overgeslagen en is de aanpak efficiënter dan een volledige in-orderscan.
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 = 32Knopen in een bereik tellen
Knopen in een bereik [low, high] tellen volgt dezelfde logica voor het overslaan van deelbomen. Een alternatief gebruikt bisect_left/bisect_right op de in-orderarray, maar een directe BST-doorloop kost O(log n + k), terwijl het eerst omzetten naar een array altijd O(n) kost. Kies voor een directe doorloop, tenzij je veel bereikopvragingen moet beantwoorden. In dat geval kun je een uitgebreide BST bouwen met aantallen per deelboom, zodat elke opvraging O(log n) kost.
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 = 3BST omzetten naar een gesorteerde array (volledig algoritme)
Een BST omzetten naar een gesorteerde array kost O(n) tijd en O(n) ruimte. Gebruik een in-orderdoorloop en voeg elke waarde toe. Dit is het startpunt voor problemen met meerdere stappen, zoals 'twee BST's samenvoegen', 'de mediaan van een BST vinden' of 'controleren of twee BST's dezelfde in-orderreeks hebben'. De resulterende array ondersteunt toegang in O(1) via een index, binair zoeken en technieken met twee aanwijzers die de BST zelf niet rechtstreeks kan bieden.
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)Uitgebreide BST: groottes van deelbomen
Een uitgebreide BST slaat bij elke knoop extra informatie op, zoals de grootte van de deelboom ervan. Met groottes van deelbomen kun je de k-de kleinste waarde in O(log n) vinden: kijk bij elke knoop of de grootte van de linker deelboom k-1 is; dan is de huidige knoop het antwoord. Is de grootte van de linker deelboom minstens k, ga dan recursief naar links; trek anders de grootte af en ga recursief naar rechts. Dit is de datastructuur achter ordestatistiekbomen, die worden gebruikt bij competitief programmeren.
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')Alle waarden in een BST tussen twee knopen vinden
Om alle waarden terug te geven die strikt tussen twee knopen p en q liggen (waarbij p.val < q.val), combineer je een in-order-doorloop met snoeien op bereik: begin waarden te verzamelen zodra je p.val voorbij bent en stop na q.val. Dit is een veralgemening van de bereiksom en levert de gesorteerde reeks tussen de twee opgevraagde waarden in O(h + k) tijd.
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]Mediaan van een BST
De mediaan van een BST is de middelste waarde van de in-order-doorloop. Voor n knopen staat de mediaan op index n // 2 (met indexering vanaf 0). Je kunt de volledige gesorteerde array verzamelen en daarin op die index zoeken, of twee doorlopen gebruiken: tel eerst n knopen en voer daarna een tweede in-order-doorloop uit die stopt bij de n // 2-de knoop. Je kunt ook de k-de kleinste waarde gebruiken met 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 waarden die het dichtst bij het doel liggen
Vind de k waarden in een BST die het dichtst bij een doelwaarde liggen. Een aanpak met twee aanwijzers bestaat uit het omzetten naar een gesorteerde array en het gebruiken van een schuivend venster met grootte k. Je kunt ook een max-heap met grootte k gebruiken waarin je afstanden toevoegt en waarden verwijdert zodra de grootte groter wordt dan k. De aanpak met een gesorteerde array kost O(n) tijd en is eenvoudig; de aanpak met een heap kost O(n log k), maar werkt in een streamingcontext.
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]De volgorde van opvolgers benut
Veel BST-opgaven komen neer op het vinden van het volgende of vorige element in gesorteerde volgorde — bewerkingen die je met BST-navigatie in O(log n) kunt uitvoeren. De iterator die je eerder hebt gebouwd, levert de volgende waarde in geamortiseerde O(1)-tijd. Door kennis van de k-de kleinste waarde, de bereiksom en de dichtstbijzijnde waarde te combineren, kun je de meeste sollicitatievragen over BST's oplossen door te vragen: 'Hoe maakt de gesorteerde volgorde van de in-order-doorloop dit eenvoudiger?' Dit metapatroon is je kompas voor het oplossen van BST-opgaven.
# 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')Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd hoe je de k-de kleinste en grootste waarden vindt met een in-order- en omgekeerde in-order-doorloop in O(h+k), hoe je een bereiksom met BST-snoeiing gebruikt voor efficiënte bereikopvragingen en hoe je een BST omzet naar een gesorteerde array als basis voor arraygebaseerde algoritmen. Hierna verkennen we heaps en prioriteitswachtrijen.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “K-de kleinste, rangesom en BST naar gesorteerde array” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “K-de kleinste, rangesom en BST naar gesorteerde array”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “K-de kleinste, rangesom en BST naar gesorteerde array”?
Benut de gesorteerde in-order traversal om het k-de kleinste element te vinden in O(k) en waarden binnen een bereik op te tellen in O(log n + k). Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “K-de kleinste, rangesom en BST naar gesorteerde array”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- BST invoegen en zoeken
- BST verwijderen: drie gevallen
- BST valideren en in-order-eigenschappen
- K-de kleinste, rangesom en BST naar gesorteerde array