K-kleinstes Element, Bereichssumme und BST zu sortiertem Array
Nutzen Sie die sortierte In-Order-Traversierung, um das k-kleinste Element in O(k) zu finden und Werte innerhalb eines Bereichs in O(log n + k) zu summieren.
K-kleinstes Element, Bereichssumme und BST zu sortiertem Array ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
k-kleinstes Element in einem BST
Kth Smallest Element in a BST (LeetCode #230) ist eine klassische Aufgabe, die direkt die sortierte Inorder-Traversierung nutzt. Da die Inorder-Traversierung die Knoten in aufsteigender Reihenfolge besucht, zählen wir die Knoten während der Traversierung und geben den Wert beim Zählerstand k zurück. Die Laufzeit beträgt O(h + k), wobei h die Höhe des Baums (bis zum Erreichen des am weitesten links stehenden Knotens) und k die Anzahl der Schritte bei der Inorder-Traversierung ist.
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-kleinstes Element: iterativ mit einem Stack
Die iterative Variante verwendet das Inorder-Muster mit einem expliziten Stack. Legen Sie Knoten nach links auf den Stack, bis null erreicht ist, und entfernen Sie anschließend den obersten Knoten, um ihn zu zählen. Wenn der Zähler k erreicht, geben Sie den Wert des aktuellen Knotens zurück. Dadurch wird Pythons Rekursionslimit bei sehr tiefen Bäumen vermieden. Zeitaufwand und Speicherbedarf betragen weiterhin O(h + k) bzw. O(h). Nach der rekursiven Variante fragen Interviewer häufig auch nach der iterativen.
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)) # 3k-größtes Element in einem BST
Kth Largest verwendet eine umgekehrte Inorder-Traversierung (rechts → Wurzel → links), bei der die Knoten in absteigender Reihenfolge besucht werden. Zählen Sie k Schritte und geben Sie den Wert des aktuellen Knotens zurück. Dies ist das Gegenstück zum k-kleinsten Element und benötigt O(h + k) Zeit. Alternativ können Sie kth_smallest(root, total_count - k + 1) berechnen, wenn Sie die Größe des Baums kennen; die umgekehrte Inorder-Traversierung ist jedoch 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)Bereichssumme eines BST
Range Sum of BST (LeetCode #938) verlangt die Summe aller Werte in [low, high]. Nutzen Sie die BST-Eigenschaft, um Teilbäume abzuschneiden: Wenn der Wert des aktuellen Knotens kleiner als low ist, liegt der gesamte linke Teilbaum ebenfalls unter low – überspringen Sie ihn. Wenn der aktuelle Wert größer als high ist, überspringen Sie den rechten Teilbaum. Dadurch werden viele Zweige abgeschnitten, und der Ansatz ist effizienter als eine vollständige Inorder-Traversierung.
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 = 32Knoten in einem Wertebereich zählen
Das Zählen von Knoten in einem Bereich [low, high] folgt derselben Logik zum Abschneiden von Teilbäumen. Alternativ können Sie bisect_left/bisect_right auf dem Inorder-Array verwenden – die direkte BST-Traversierung benötigt jedoch O(log n + k), während die vorherige Umwandlung in ein Array immer O(n) benötigt. Wählen Sie die direkte Traversierung, es sei denn, Sie müssen viele Bereichsabfragen beantworten. In diesem Fall ermöglicht ein erweiterter BST mit Teilbaumzählungen O(log n) pro Abfrage.
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 in ein sortiertes Array umwandeln (vollständiger Algorithmus)
Die Umwandlung eines BST in ein sortiertes Array benötigt O(n) Zeit und O(n) Speicher. Verwenden Sie eine Inorder-Traversierung und fügen Sie jeden Wert hinzu. Dies ist der Ausgangspunkt für mehrstufige Aufgaben: „zwei BSTs zusammenführen“, „den Median eines BST finden“ oder „prüfen, ob zwei BSTs dieselbe Inorder-Folge haben“. Das resultierende Array unterstützt den Zugriff per Index in O(1), binäre Suche und Zwei-Zeiger-Techniken, die der BST selbst nicht direkt bereitstellt.
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)Erweiterter BST: Teilbaumgrößen
Ein erweiterter BST speichert zusätzliche Informationen an jedem Knoten, etwa die Größe seines Teilbaums. Mit Teilbaumgrößen lässt sich das k-kleinste Element in O(log n) bestimmen: Ist die Größe des linken Teilbaums an einem Knoten k-1, ist der aktuelle Knoten die Antwort; ist die Größe des linken Teilbaums >= k, wird links weitergesucht; andernfalls zieht man die Größe des linken Teilbaums ab und sucht rechts weiter. Diese Datenstruktur bildet die Grundlage von Order-Statistic-Trees, die im Competitive Programming verwendet werden.
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 Werte im BST zwischen zwei Knoten finden
Um alle Werte strikt zwischen zwei Knoten p und q zurückzugeben (wobei p.val < q.val gilt), kombinieren Sie eine Inorder-Traversierung mit Bereichs-Pruning: Beginnen Sie mit dem Sammeln von Werten, sobald Sie p.val überschreiten, und hören Sie nach q.val auf. Dies ist eine Verallgemeinerung der Bereichssumme und liefert die sortierte Folge zwischen den beiden Abfragewerten in O(h + k) Zeit.
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]Median eines BST
Der Median eines BST ist der mittlere Wert der Inorder-Traversierung. Bei n Knoten befindet sich der Median am Index n // 2 (beginnend bei Index 0). Sie können entweder das vollständige sortierte Array sammeln und per Index darauf zugreifen oder zwei Durchläufe verwenden: Zählen Sie zunächst n Knoten und führen Sie dann eine zweite Inorder-Traversierung durch, die beim n // 2-ten Knoten endet. Alternativ können Sie das k-kleinste Element mit k = n // 2 + 1 verwenden.
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])Die k nächstgelegenen Werte zum Zielwert
Finden Sie die k Werte in einem BST, die einem Zielwert am nächsten liegen. Ein Ansatz mit zwei Zeigern besteht darin, den BST in ein sortiertes Array umzuwandeln und ein gleitendes Fenster der Größe k zu verwenden. Alternativ können Sie einen Max-Heap der Größe k verwenden, in den Sie Abstände einfügen und Elemente entfernen, sobald seine Größe k überschreitet. Der Ansatz mit dem sortierten Array benötigt O(n) Zeit und ist einfach; der Heap-Ansatz benötigt O(n log k), funktioniert aber in einem Streaming-Kontext.
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]Ordnungsprinzip des Nachfolgers genutzt
Viele BST-Probleme lassen sich auf das Finden des nächsten oder vorherigen Elements in sortierter Reihenfolge reduzieren – Operationen, die sich durch BST-Navigation in O(log n) ausführen lassen. Der zuvor erstellte Iterator liefert das nächste Element amortisiert in O(1). Wenn Sie Wissen über das k-kleinste Element, die Bereichssumme und nächstgelegene Werte kombinieren, können Sie die meisten BST-Interviewaufgaben lösen, indem Sie fragen: „Wie vereinfacht die sortierte Reihenfolge der Inorder-Traversierung dieses Problem?“ Dieses Meta-Muster dient Ihnen als Orientierung bei der Lösung von BST-Problemen.
# 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')Schnelltest
Überprüfen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: das k-kleinste und k-größte Element mithilfe der Inorder- und umgekehrten Inorder-Traversierung in O(h+k), die Bereichssumme mit BST-Pruning für effiziente Bereichsabfragen sowie die Umwandlung eines BST in ein sortiertes Array als Grundlage für arraybasierte Algorithmen. Als Nächstes beschäftigen wir uns mit Heaps und Prioritätswarteschlangen.
Häufig gestellte Fragen
Ist die Lektion „K-kleinstes Element, Bereichssumme und BST zu sortiertem Array“ kostenlos?
Ja — der vollständige Text von „K-kleinstes Element, Bereichssumme und BST zu sortiertem Array“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „K-kleinstes Element, Bereichssumme und BST zu sortiertem Array“?
Nutzen Sie die sortierte In-Order-Traversierung, um das k-kleinste Element in O(k) zu finden und Werte innerhalb eines Bereichs in O(log n + k) zu summieren. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „K-kleinstes Element, Bereichssumme und BST zu sortiertem Array“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- BST-Einfügen und -Suchen
- BST-Löschen: drei Fälle
- BST und In-Order-Eigenschaften validieren
- K-kleinstes Element, Bereichssumme und BST zu sortiertem Array