Soal-soal BST

Soal BST pada wawancara menggumpal di tiga pola, yaitu validasi BST, kueri rentang, dan pencarian elemen terkecil ke-k. Ketiganya berdiri di atas dua fasilitas dari bahasan BST, yaitu invarian kiri < node < kanan dan penelusuran inorder yang menghasilkan urutan naik. Kesalahan paling mahal ada pada validasi, karena versi naifnya meloloskan pohon yang sebenarnya salah tanpa menimbulkan error apa pun. Diagram pada kueri rentang menunjukkan pemangkasan cabang yang memanfaatkan invarian demi kecepatan.

Validasi BST dengan batas rentang#

Pemeriksa paling menggoda membandingkan setiap node dengan dua anak langsungnya, dan pemeriksa itu keliru. Invarian menuntut seluruh subtree kiri dan kanan patuh, bukan hanya keturunan satu level, sehingga nilai yang bermasalah bisa bersembunyi dua level di bawah. Pohon contoh memuat nilai 6 di subtree kanan dari 10, tetapi 6 masih lebih kecil dari induk langsungnya 15 sehingga cek naif meloloskannya. Versi yang benar mengoper batas terbuka (bawah, atas) ke setiap pemanggilan rekursif. Subtree kiri menerima batas atas baru berupa nilai node, subtree kanan menerima batas bawah baru, dan setiap node wajib berada di dalam rentangnya.

"""Validasi BST: versi naif yang keliru dan versi batas rentang yang benar."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def is_bst_naif(akar):
    # versi keliru: hanya membandingkan node dengan anak langsungnya
    if akar is None:
        return True
    if akar.kiri is not None and akar.kiri.nilai >= akar.nilai:
        return False
    if akar.kanan is not None and akar.kanan.nilai <= akar.nilai:
        return False
    return is_bst_naif(akar.kiri) and is_bst_naif(akar.kanan)

def is_bst(akar, bawah=None, atas=None):
    # versi benar: setiap node wajib berada di rentang terbuka (bawah, atas)
    if akar is None:
        return True
    if bawah is not None and akar.nilai <= bawah:
        return False
    if atas is not None and akar.nilai >= atas:
        return False
    return (is_bst(akar.kiri, bawah, akar.nilai)
            and is_bst(akar.kanan, akar.nilai, atas))

# pohon yang lolos pemeriksaan naif tetapi melanggar invarian BST
salah = Node(10)
salah.kiri = Node(5)
salah.kanan = Node(15)
salah.kanan.kiri = Node(6)     # 6 berada di subtree kanan dari 10, padahal 6 < 10
salah.kanan.kanan = Node(20)

print("pemeriksa naif :", is_bst_naif(salah))
print("pemeriksa batas:", is_bst(salah))

pemeriksa naif : True
pemeriksa batas: False

Keluaran menunjukkan kedua pemeriksa berbeda pada pohon yang sama, True melawan False, dan versi batas pulalah yang benar. Fungsi is_bst mengoper bawah dan atas dalam satu perjalanan DFS tanpa penelusuran inorder tambahan, sehingga biayanya tetap $O(n)$ karena setiap node dikunjungi sekali. Konvensi rentang terbuka dipilih agar nilai pembatas tidak ikut lolos, dan pilihan ini sekaligus menegaskan perlakuan terhadap duplikat. Pemeriksa naif tidak sekadar kurang teliti. Keluarannya berupa jawaban yang salah dengan penuh percaya diri, dan itulah jenis bug yang paling sulit dilacak.

Kueri rentang dengan pemangkasan#

Kueri rentang mengumpulkan seluruh nilai dalam $[lo, hi]$ sambil memanfaatkan invarian untuk melewati cabang yang mustahil memuat jawaban. Bila nilai node masih di atas lo, subtree kirinya masih mungkin memuat nilai sah, sedangkan bila node sudah di bawah lo, seluruh subtree kirinya pasti di bawah lo dan boleh dilewati. Simetri yang sama berlaku di sisi kanan. Diagram berikut menandai kueri $[30, 65]$ pada BST standar, dengan cabang menuju 20 dan 80 ditandai dipangkas karena mustahil memuat jawaban.

"""Kueri rentang pada BST: kumpulkan nilai dalam [lo, hi] dengan pemangkasan cabang."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def kueri_rentang(akar, lo, hi, hasil):
    if akar is None:
        return
    if akar.nilai > lo:
        # subtree kiri masih mungkin memuat nilai dalam rentang
        kueri_rentang(akar.kiri, lo, hi, hasil)
    if lo <= akar.nilai <= hi:
        hasil.append(akar.nilai)
    if akar.nilai < hi:
        # subtree kanan masih mungkin memuat nilai dalam rentang
        kueri_rentang(akar.kanan, lo, hi, hasil)

# BST standar dibangun manual
n = {v: Node(v) for v in [50, 30, 70, 20, 40, 60, 80]}
n[50].kiri, n[50].kanan = n[30], n[70]
n[30].kiri, n[30].kanan = n[20], n[40]
n[70].kiri, n[70].kanan = n[60], n[80]
akar = n[50]

hasil = []
kueri_rentang(akar, 30, 65, hasil)
print("rentang [30, 65] :", hasil)

hasil = []
kueri_rentang(akar, 45, 90, hasil)
print("rentang [45, 90] :", hasil)

rentang [30, 65] : [30, 40, 50, 60]
rentang [45, 90] : [50, 60, 70, 80]

Pada rentang $[30, 65]$, node 20 dan 80 tidak pernah dikunjungi karena cabangnya dipangkas dari atas, sedangkan node 70 tetap dikunjungi untuk mencapai 60 tetapi tidak dikumpulkan karena berada di luar rentang. Rentang $[45, 90]$ memangkas cabang menuju 20 sejak node 30 lalu menyapu sisi kanan sampai 80. Kondisi pemangkasan ditulis ketat: akar.nilai > lo memicu perjalanan ke kiri dan akar.nilai < hi memicu perjalanan ke kanan, sehingga nilai tepat pada batas tetap dikumpulkan tanpa kunjungan sia-sia. Pada BST seimbang, kueri rentang berjalan dalam $O(h + m)$ dengan $m$ banyaknya jawaban, jauh lebih murah daripada inorder penuh $O(n)$ bila rentangnya sempit.

Elemen terkecil ke-k#

Inorder pada BST menghasilkan nilai terurut naik, sehingga elemen terkecil ke-k adalah node ke-k yang dikunjungi inorder. Menampung seluruh urutan lalu mengambil indeks ke-k memang bekerja, tetapi menyimpan $O(n)$ nilai yang sebagian besar tidak diperlukan. Versi hemat menghitung kunjungan sambil berjalan dan berhenti tepat pada hitungan ke-k, dengan penanda jawaban yang membuat seluruh cabang tersisa langsung kembali tanpa bekerja.

"""Elemen terkecil ke-k pada BST: inorder dihentikan pada kunjungan ke-k."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def inorder_daftar(akar):
    hasil = []
    def rek(node):
        if node is not None:
            rek(node.kiri)
            hasil.append(node.nilai)
            rek(node.kanan)
    rek(akar)
    return hasil

def k_terkecil(akar, k):
    hitung = 0
    jawaban = None

    def inorder(node):
        nonlocal hitung, jawaban
        if node is None or jawaban is not None:
            return   # berhenti segera setelah jawaban ditemukan
        inorder(node.kiri)
        if jawaban is not None:
            return
        hitung += 1
        if hitung == k:
            jawaban = node.nilai
            return
        inorder(node.kanan)

    inorder(akar)
    return jawaban

# BST standar dibangun manual
n = {v: Node(v) for v in [50, 30, 70, 20, 40, 60, 80]}
n[50].kiri, n[50].kanan = n[30], n[70]
n[30].kiri, n[30].kanan = n[20], n[40]
n[70].kiri, n[70].kanan = n[60], n[80]
akar = n[50]

print("inorder (naik) :", " ".join(str(x) for x in inorder_daftar(akar)))
print("terkecil ke-1  :", k_terkecil(akar, 1))
print("terkecil ke-3  :", k_terkecil(akar, 3))
print("terkecil ke-5  :", k_terkecil(akar, 5))

inorder (naik) : 20 30 40 50 60 70 80
terkecil ke-1  : 20
terkecil ke-3  : 40
terkecil ke-5  : 60

Fungsi k_terkecil menampung hitungan dan jawaban lewat nonlocal sehingga kedua nilai hidup di luar fungsi inorder yang bersarang. Pemeriksaan jawaban is not None dilakukan dua kali, sebelum dan sesudah penelusuran kiri, agar tidak ada kunjungan tersisa yang menambah hitungan setelah jawaban ditemukan. Keluaran menempatkan 40 sebagai jawaban ke-3 dan 60 sebagai jawaban ke-5, keduanya dapat dicek langsung pada baris inorder di atasnya. Pola berhenti dini ini dipakai berulang pada soal pohon lain yang menanyakan kunjungan ke-k, termasuk varian yang mencari elemen terbesar ke-k.

Varian Java#

public class ValidasiBST {
    static class Node {
        int nilai;
        Node kiri, kanan;
        Node(int nilai) { this.nilai = nilai; }
    }

    // setiap node wajib berada di rentang terbuka (bawah, atas)
    static boolean isBst(Node node, Integer bawah, Integer atas) {
        if (node == null) return true;
        if (bawah != null && node.nilai <= bawah) return false;
        if (atas != null && node.nilai >= atas) return false;
        return isBst(node.kiri, bawah, node.nilai)
                && isBst(node.kanan, node.nilai, atas);
    }

    public static void main(String[] args) {
        // pohon yang lolos pemeriksaan naif tetapi bukan BST
        Node akar = new Node(10);
        akar.kiri = new Node(5);
        akar.kanan = new Node(15);
        akar.kanan.kiri = new Node(6);
        akar.kanan.kanan = new Node(20);
        System.out.println("valid : " + isBst(akar, null, null));
    }
}

valid : false

Versi Java membuktikan bahwa teknik batas rentang berpindah bahasa tanpa perubahan bentuk. Tipe Integer dipilih untuk bawah dan atas agar nilainya bisa null, padanan None pada Python, sehingga pemeriksaan pembatas dilakukan dengan null check. Pohon contoh yang sama, yaitu 10 dengan anak 5 dan 15 serta 6 dan 20 di bawah 15, dilaporkan false sesuai keluaran Python. Pada pohon yang sah seperti 50, 30, 70, 20, 40, 60, 80, fungsi yang sama mengembalikan true tanpa perubahan kode apa pun. Keluaran satu kata ini memang pendek, tetapi kebenarannya menopang seluruh operasi BST lain yang menyandarkan diri pada invarian.

Kesalahan umum#

1. Mengandalkan pemeriksaan anak langsung saat validasi. Contoh pohon pada bagian validasi lolos cek naif padahal melanggar invarian, dan kesalahan ini tidak memunculkan error. Oper batas rentang terbuka pada setiap pemanggilan rekursif.
2. Memakai rentang tertutup yang salah arah. Mengoper batas dengan <= membuat nilai duplikat lolos atau node pembatas ditolak dengan alasan yang keliru. Karena itu, tetapkan konvensi rentang terbuka dan pertahankan dari akar hingga leaf.
3. Mengumpulkan seluruh inorder untuk soal ke-k. Menampung seluruh nilai menyita $O(n)$ memori padahal k kecil, dan penghentian dini dengan penghitung menyelesaikannya tanpa penyimpanan ekstra.
4. Menukar arah pengoperan batas. Subtree kiri menerima batas atas baru dan subtree kanan menerima batas bawah baru. Menukar keduanya membuat validator menolak pohon yang sah atau meloloskan pohon yang salah.

Ringkasan#

• Validasi BST menuntut batas rentang terbuka yang mengalir turun ke setiap node, bukan perbandingan anak langsung.
• Kueri rentang memangkas cabang yang mustahil dan berjalan dalam $O(h + m)$ pada BST seimbang.
• Elemen terkecil ke-k adalah kunjungan inorder ke-k, diselesaikan dengan penghitung dan penghentian dini.
• Teknik yang sama berpindah antar Python dan Java tanpa perubahan bentuk, cukup menyesuaikan penanda kosongnya.

Referensi#

• Binary search tree — Wikipedia — rincian invarian yang menjadi dasar validasi, kueri rentang, dan urutan inorder.
• NeetCode roadmap — peta soal pohon dan BST untuk latihan lanjutan setelah ketiga pola dikuasai.