Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut
Manfaatkan traversal in-order terurut untuk menemukan elemen terkecil ke-k dalam O(k) dan menjumlahkan nilai dalam rentang dalam O(log n + k).
Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Elemen Terkecil ke-K dalam BST
Elemen Terkecil ke-K dalam BST (LeetCode #230) adalah masalah klasik yang secara langsung memanfaatkan penelusuran urutan-tengah terurut. Karena penelusuran urutan-tengah mengunjungi simpul dalam urutan menaik, kita cukup menghitung simpul selama penelusuran dan mengembalikan nilai pada hitungan k. Waktunya adalah O(h + k), dengan h sebagai tinggi pohon (untuk mencapai simpul paling kiri) dan k sebagai jumlah langkah dalam penelusuran urutan-tengah.
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)) # 2Elemen Terkecil ke-K: Secara Iteratif dengan Tumpukan
Versi iteratif menggunakan pola urutan-tengah dengan tumpukan eksplisit. Dorong simpul-simpul kiri hingga mencapai kondisi kosong, lalu ambil elemen teratas dan hitung. Saat hitungan mencapai k, kembalikan nilai simpul saat ini. Cara ini menghindari batas rekursi Python untuk pohon yang sangat dalam dan memiliki waktu O(h + k) serta ruang O(h) yang sama. Pewawancara sering meminta versi iteratif setelah versi rekursif.
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)) # 3Elemen Terbesar ke-K dalam BST
Elemen Terbesar ke-K menggunakan penelusuran urutan-tengah terbalik (kanan → akar → kiri), yang mengunjungi simpul dalam urutan menurun. Hitung k langkah dan kembalikan nilai simpul saat ini. Cara ini merupakan kebalikan dari elemen terkecil ke-k dan berjalan dalam waktu O(h + k). Sebagai alternatif, hitung kth_smallest(root, total_count - k + 1) jika Anda mengetahui ukuran pohon, tetapi pendekatan urutan-tengah terbalik lebih elegan.
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)Jumlah Nilai dalam Rentang BST
Jumlah Nilai dalam Rentang BST (LeetCode #938) meminta jumlah semua nilai dalam [low, high]. Manfaatkan sifat BST untuk melakukan pemangkasan: jika nilai simpul saat ini lebih kecil daripada low, seluruh subpohon kiri juga berada di bawah low—lewati subpohon tersebut. Jika nilai saat ini lebih besar daripada high, lewati subpohon kanan. Cara ini memangkas banyak cabang dan lebih efisien daripada pemindaian urutan-tengah secara menyeluruh.
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 = 32Menghitung Simpul dalam Rentang
Menghitung simpul dalam rentang [low, high] mengikuti logika pemangkasan yang sama. Alternatifnya, gunakan bisect_left/bisect_right pada larik urutan-tengah—tetapi penelusuran BST langsung memerlukan O(log n + k), sedangkan mengonversi ke larik terlebih dahulu selalu memerlukan O(n). Pilih penelusuran langsung, kecuali Anda perlu menjawab banyak kueri rentang; dalam kasus tersebut, membangun BST yang diperkaya dengan jumlah simpul subpohon memungkinkan O(log n) untuk setiap kueri.
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 ke Larik Terurut (Algoritma Lengkap)
Mengonversi BST menjadi larik terurut memerlukan waktu O(n) dan ruang O(n). Gunakan penelusuran urutan-tengah dan lakukan append untuk setiap nilai. Ini merupakan titik awal untuk soal bertahap: 'gabungkan dua BST', 'temukan median BST', atau 'periksa apakah dua BST memiliki urutan urutan-tengah yang sama'. Larik hasilnya mendukung akses O(1) berdasarkan indeks, pencarian biner, dan teknik dua penunjuk yang tidak dapat disediakan BST secara langsung.
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)BST Teraugmentasi: Ukuran Subpohon
BST teraugmentasi menyimpan informasi tambahan pada setiap simpul, seperti ukuran subpohonnya. Dengan ukuran subpohon, kth-smallest dapat dilakukan dalam O(log n): pada setiap simpul, jika ukuran subpohon kiri adalah k-1, simpul saat ini adalah jawabannya; jika ukuran subpohon kiri >= k, lanjutkan secara rekursif ke kiri; jika tidak, kurangi k dan lanjutkan ke kanan. Inilah struktur data yang mendasari pohon statistik urutan yang digunakan dalam pemrograman kompetitif.
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')Menemukan Semua Nilai dalam BST di Antara Dua Simpul
Untuk mengembalikan semua nilai yang berada tepat di antara dua simpul p dan q (dengan p.val < q.val), gabungkan penelusuran inorder dengan pemangkasan rentang: mulai kumpulkan nilai setelah melewati p.val dan berhenti setelah q.val. Ini merupakan generalisasi dari jumlah rentang dan menghasilkan urutan terurut di antara dua nilai kueri dalam time 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]Median BST
Median sebuah BST adalah nilai tengah dari penelusuran inorder. Untuk n simpul, median berada pada indeks n // 2 (dengan indeks dimulai dari 0). Anda dapat mengumpulkan seluruh larik terurut lalu mengambil nilai berdasarkan indeks tersebut, atau menggunakan dua lintasan: pertama, hitung n simpul, lalu lakukan penelusuran inorder kedua dan berhenti pada simpul ke-n // 2. Alternatifnya, gunakan kth-smallest dengan 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])K Nilai Terdekat dengan Target
Temukan k nilai dalam sebuah BST yang paling dekat dengan target. Salah satu pendekatan menggunakan dua penunjuk: ubah BST menjadi larik terurut, lalu gunakan jendela geser berukuran k. Alternatifnya, gunakan tumpukan maksimum berukuran k; masukkan jarak dengan push dan lakukan pop ketika ukurannya melebihi k. Pendekatan larik terurut memerlukan time O(n) dan sederhana; pendekatan tumpukan memerlukan O(n log k), tetapi dapat digunakan dalam konteks aliran data.
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]Pemanfaatan Sifat Urutan Penerus
Banyak masalah BST dapat disederhanakan menjadi pencarian elemen berikutnya atau sebelumnya dalam urutan terurut—operasi yang memerlukan O(log n) dengan navigasi BST. Pengiterasi yang kita buat sebelumnya memberikan operasi berikutnya dengan time O(1) secara diamortisasi. Dengan menggabungkan kth-smallest, jumlah rentang, dan pengetahuan tentang nilai terdekat, Anda dapat menyelesaikan sebagian besar masalah BST dalam wawancara dengan bertanya: “Bagaimana pengurutan traversal inorder menyederhanakan masalah ini?” Pola meta ini menjadi kompas Anda dalam memecahkan masalah 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')Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: kth smallest dan largest menggunakan penelusuran inorder dan reverse inorder dalam O(h+k), jumlah rentang dengan pemangkasan BST untuk kueri rentang yang efisien, serta cara mengubah BST menjadi larik terurut sebagai dasar algoritme berbasis larik. Selanjutnya, kita akan membahas tumpukan dan antrean prioritas.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut” gratis?
Ya — teks lengkap “Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut”?
Manfaatkan traversal in-order terurut untuk menemukan elemen terkecil ke-k dalam O(k) dan menjumlahkan nilai dalam rentang dalam O(log n + k). Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Penyisipan dan Pencarian BST
- Penghapusan BST: Tiga Kasus
- Memvalidasi BST dan Sifat In-Order
- Elemen ke-K Terkecil, Jumlah Rentang, dan BST menjadi Array Terurut