Wawancara Coding: Serialisasi dan Deserialisasi Pohon Biner

Masalah dan Konteks yang Berlaku

Implementasikan dua fungsi untuk pohon biner arbitrer:

• serialize(root) mengonversi pohon menjadi sebuah string.
• deserialize(data) merekonstruksi pohon dengan nilai dan bentuk yang sama.

Asumsikan nilai node adalah bilangan bulat bertanda 32-bit, pohon mungkin kosong, dan string hasil serialisasi hanya perlu dapat dioperasikan dengan dekoder ini. Untuk implementasi wawancara yang rekursif, asumsikan tinggi pohon sesuai dengan batas call-stack bahasa yang digunakan. Dekoder di bawah ini juga menolak teks yang tidak valid alih-alih diam-diam menerima pohon yang tidak lengkap.

Untuk pohon ini:

1
       / \
      2   3
         / \
        4   5

format yang dipilih adalah:

1,2,#,#,3,4,#,#,5,#,#

Setiap bilangan bulat mencatat sebuah node, # mencatat anak yang tidak ada, koma memisahkan token, dan preorder menentukan cara token dikonsumsi. Materi publik yang diperbarui pada tahun 2026 menyajikan masalah persis ini dengan solusi preorder dan level-order, sementara rekaman wawancara di interviewing.io menunjukkannya ditanyakan dalam wawancara simulasi dengan seorang insinyur Meta. Hal ini mendukungnya sebagai latihan coding representatif yang masih relevan tanpa mengklaim bahwa setiap perusahaan atau wawancara menggunakannya.

Apa yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah kandidat mendefinisikan reversibilitas sebelum memilih traversal. Nilai preorder saja tidak mencukupi. Sebuah root 1 dengan anak kiri 2 dan sebuah root 1 dengan anak kanan 2 keduanya menghasilkan [1, 2] kecuali anak yang tidak ada dikodekan. Bentuk yang sudah ditandai berbeda:

Left child:  1,2,#,#,#
Right child: 1,#,2,#,#

Sinyal kedua adalah merancang enkoder dan dekoder sebagai invers satu sama lain. Dalam preorder, dekoder membaca satu token. # menyelesaikan subpohon kosong. Sebuah nilai memulai sebuah node, setelah itu subpohon lengkap berikutnya menjadi milik anak kiri dan subpohon lengkap setelahnya menjadi milik anak kanan. Format ini dengan demikian menyediakan batas rekursifnya sendiri tanpa menyimpan panjang subpohon.

Sinyal ketiga adalah argumen kebenaran yang nyata. Untuk pohon dengan n node, terdapat n + 1 pointer anak null, sehingga pengkodean mengandung tepat 2n + 1 token. Yang lebih penting, dekoder harus mengonsumsi tepat token untuk satu subpohon dan meninggalkan iterator yang diposisikan pada subpohon berikutnya. Induksi struktural membuktikan properti tersebut.

Terakhir, pewawancara mencari batas-batas rekayasa: masukan tidak valid, nilai negatif dan duplikat, kedalaman rekursi, ukuran keluaran, dan kapan BFS atau format serialisasi produksi adalah pilihan yang lebih baik.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah ini pohon biner arbitrer atau binary search tree? Pohon arbitrer memerlukan

penanda struktural. BST terkadang dapat direkonstruksi dari preorder ditambah kebijakan duplikat yang eksplisit.

• Apakah string harus mengikuti format wire yang sudah ada? Prompt ini mengizinkan format privat.

Penyimpanan lintas layanan memerlukan pembuatan versi skema, aturan kompatibilitas, dan sering kali codec standar.

• Apakah nilai node dapat mengandung delimiter atau sentinel? Mereka adalah bilangan bulat, jadi koma dan #

tidak ambigu. String umum memerlukan escaping atau length prefix.

• Apakah pohon bisa kosong? Ya. Pohon tersebut diserialisasi menjadi #.
• Apakah masukan bisa sangat dalam atau bersifat adversarial? Jawaban rekursif mengasumsikan tinggi yang terbatas.

Pohon yang tidak dipercaya atau sangat miring memerlukan stack eksplisit dan batas sumber daya.

• Apakah deserialize hanya akan menerima keluaran tepercaya dari serialize? Kode tetap ketat:

teks kosong, bilangan bulat tidak valid, pohon yang terpotong, dan token yang tersisa ditolak.

• Apakah kita mengoptimalkan untuk keterbacaan atau byte minimum? Teks preorder mudah dijelaskan dan diuji.

Protokol biner yang kompak akan mengkodekan tag dan bilangan bulat secara berbeda.

Kerangka Jawaban 30 Detik

"Saya akan menggunakan traversal preorder dan memancarkan # untuk setiap anak yang tidak ada. Token nilai berarti membuat sebuah node, lalu secara rekursif mendekode subpohon kiri dan kanannya; # berarti kembalikan None. Penanda null diperlukan karena nilai saja tidak dapat membedakan anak kiri dari anak kanan. Enkoder dan dekoder saling mencerminkan satu sama lain, dan induksi struktural menunjukkan bahwa setiap panggilan decode mengonsumsi tepat satu subpohon. Kedua operasi membutuhkan waktu O(n) dan menghasilkan data O(n), dengan call stack O(h) untuk tinggi h. Saya juga akan menolak masukan yang terpotong atau tersisa dan menyebutkan BFS iteratif atau versi berbasis stack ketika kedalaman tidak terbatas."

Pendalaman Langkah demi Langkah

Langkah satu: tolak baseline hanya-nilai dengan contoh tandingan.

Nilai preorder, inorder, atau postorder tidak secara unik mengidentifikasi pohon biner arbitrer dengan sendirinya. Bahkan menggabungkan preorder dan inorder menjadi ambigu ketika nilai duplikat diizinkan. Format harus mengkodekan bentuk maupun nilai. Penanda null adalah sinyal bentuk paling sederhana untuk format string wawancara.

Langkah dua: pilih tata bahasa yang dapat didekode dari kiri ke kanan.

Format dapat dijelaskan secara rekursif:

tree := "#"
      | integer "," tree "," tree

Implementasi aktual melakukan tokenisasi pada koma terlebih dahulu, sehingga setiap panggilan rekursif mengonsumsi satu token dan, untuk sebuah nilai, dua pengkodean subpohon berikutnya. Teks bilangan bulat bertanda tidak pernah mengandung , atau #. Pohon kosong adalah #; sebuah leaf dengan nilai 7 adalah 7,#,#.

Tata bahasa ini juga memberikan invariant penghitungan yang berguna. Pohon biner dengan n node nyata memiliki n + 1 pointer anak null. Serialisasi oleh karena itu memancarkan n token nilai dan n + 1 token null, untuk total 2n + 1 token. Jumlah ini adalah diagnostik, bukan pengganti untuk parsing: token yang tidak valid tetap dapat memiliki total yang ganjil.

Langkah tiga: implementasikan operasi rekursif yang saling mencerminkan.

from __future__ import annotations

from dataclasses import dataclass


MIN_INT32 = -(2**31)
MAX_INT32 = 2**31 - 1


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


class Codec:
    NULL = "#"
    SEP = ","

    def serialize(self, root: TreeNode | None) -> str:
        tokens: list[str] = []

        def visit(node: TreeNode | None) -> None:
            if node is None:
                tokens.append(self.NULL)
                return

            if node.val < MIN_INT32 or node.val > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            tokens.append(str(node.val))
            visit(node.left)
            visit(node.right)

        visit(root)
        return self.SEP.join(tokens)

    def deserialize(self, data: str) -> TreeNode | None:
        if data == "":
            raise ValueError("serialization cannot be empty")

        tokens = iter(data.split(self.SEP))

        def build() -> TreeNode | None:
            try:
                token = next(tokens)
            except StopIteration:
                raise ValueError("serialization is truncated") from None

            if token == self.NULL:
                return None

            try:
                value = int(token)
            except ValueError:
                raise ValueError(f"invalid integer token: {token}") from None

            if value < MIN_INT32 or value > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            node = TreeNode(value)
            node.left = build()
            node.right = build()
            return node

        root = build()

        try:
            extra = next(tokens)
        except StopIteration:
            return root

        raise ValueError(f"trailing token: {extra}")

Membangun daftar token menghindari penggabungan string berulang selama serialisasi. Dekoder berbagi satu iterator di antara panggilan rekursif, sehingga anak tidak memulai ulang dari awal. Memeriksa token yang tersisa setelah root selesai mencegah masukan valid-prefix seperti 1,#,#,9,#,# diterima.

Langkah empat: buktikan bahwa decoding membalikkan serialisasi.

Gunakan induksi struktural pada pohon T.

• Kasus dasar: jika T kosong, serialisasi memancarkan #. Dekoder membaca #, mengembalikan None, dan

mengonsumsi tepat satu token subpohon tersebut.

• Langkah induktif: misalkan klaim berlaku untuk subpohon kiri dan kanan. Serialisasi memancarkan

nilai root, diikuti oleh pengkodean kiri yang lengkap, kemudian pengkodean kanan yang lengkap. Dekoder membuat root yang sama, panggilan rekursif pertama mengonsumsi tepat pengkodean kiri berdasarkan hipotesis, dan yang kedua mengonsumsi tepat pengkodean kanan. Ia merekonstruksi bentuk dan nilai yang sama serta berhenti tepat setelah T.

Dengan demikian deserialize(serialize(T)) secara struktural sama dengan T, dan setiap panggilan meninggalkan iterator di subpohon berikutnya yang belum dibaca. Pemeriksaan token-tersisa akhir memverifikasi bahwa root mengonsumsi seluruh masukan.

Langkah lima: hitung biaya tanpa menyembunyikan keluaran atau stack.

Kedua operasi mengunjungi setiap node nyata dan pointer null sekali, sehingga waktu adalah O(n). Keluaran yang diserialisasi dan masukan yang ditokenisasi adalah O(n). Pohon yang direkonstruksi sendiri juga O(n). Penggunaan call-stack rekursif adalah O(h), di mana h adalah tinggi pohon: O(log n) untuk pohon seimbang dan O(n) untuk pohon yang sepenuhnya miring.

Kode rekursif adalah jawaban wawancara yang baik ketika tinggi terbatas dan kejelasan penting. Kode ini tidak aman untuk rantai yang dikendalikan penyerang yang lebih panjang dari batas rekursi runtime. Dalam kasus itu, gunakan stack eksplisit atau antrian level-order dan terapkan batas node, token, byte, dan kedalaman maksimum.

Langkah enam: bandingkan DFS preorder dengan BFS level-order.

Keduanya dapat reversibel dalam waktu O(n) dan ruang keluaran jika mempertahankan informasi null.

BFS lebih disukai ketika kedalaman rekursi adalah risiko langsung atau sistem sekitarnya sudah menggunakan representasi level-order. Preorder lebih disukai untuk wawancara dasar karena tata bahasa dan pembuktiannya lebih kecil.

Langkah tujuh: verifikasi round trip dan masukan yang tidak valid.

Pengujian round-trip harus mencakup:

Juga tolak "", 1,#, x,#,#, 2147483648,#,#, dan 1,#,#,2,#,#. Untuk pohon yang dihasilkan, bandingkan pohon asli dan yang didekode secara rekursif dan asersi serialize(deserialize(serialize(root))) == serialize(root). Pengujian pohon miring harus berjalan mendekati batas tinggi yang diterima sehingga asumsi stack terlihat jelas alih-alih kebetulan.

Contoh Jawaban Berkualitas Tinggi

"Saya terlebih dahulu akan mengonfirmasi bahwa ini adalah pohon biner arbitrer, nilai adalah bilangan bulat bertanda 32-bit, dan format hanya perlu dibaca oleh dekoder kita. Karena nilai duplikat diizinkan, saya perlu mengkodekan struktur secara eksplisit.

Saya akan melakukan traversal dalam preorder. Untuk node nyata saya memancarkan nilainya, lalu subpohon kiri dan kanannya; untuk anak yang tidak ada saya memancarkan #. Ini membedakan, misalnya, anak kiri dari anak kanan bahkan ketika nilai preorder identik. Selama decoding, satu iterator token bersama mencerminkan tata bahasa yang sama: # mengembalikan None; jika tidak, saya membuat sebuah node dan secara rekursif membangun kiri lalu kanan.

Kebenaran mengikuti dari induksi struktural. Pohon kosong adalah satu #. Untuk root nyata, dengan mengasumsikan setiap panggilan rekursif merekonstruksi dan mengonsumsi tepat satu subpohon anak, dua panggilan mengonsumsi bagian kiri dan kanan yang diserialisasi secara berurutan dan membangun kembali root aslinya. Saya akan menolak akhir prematur, nilai tidak valid atau di luar rentang, dan token yang tersisa.

Setiap node nyata dan pointer null diproses sekali, sehingga kedua operasi adalah O(n). Teks dan token menggunakan ruang O(n), sementara rekursi menggunakan stack O(h). Jika tinggi pohon dapat bersifat adversarial, saya akan beralih ke stack eksplisit atau BFS dan menerapkan batas ukuran dan kedalaman. Saya akan menguji kosong, node tunggal, hanya-kiri versus hanya-kanan, duplikat, nilai negatif, batas bilangan bulat, string yang tidak valid, dan round trip yang diacak."

Kesalahan Umum

• Serialisasi hanya nilai node → bentuk yang berbeda dapat menghasilkan traversal yang sama → **pancarkan penanda

null atau batas struktural eksplisit lainnya.**

• Menggunakan delimiter yang dapat muncul di dalam nilai → batas token menjadi ambigu → **escape

nilai, tambahkan panjang, atau pilih delimiter di luar tata bahasa nilai.**

• Membuat iterator baru di setiap panggilan rekursif → setiap anak membaca ulang token pertama →

bagikan satu iterator atau indeks yang maju.

• Mendekode root dan mengabaikan teks yang tersisa → prefix valid menyembunyikan data tersisa yang rusak →

wajibkan konsumsi masukan yang lengkap.

• Membiarkan token yang hilang muncul sebagai pengecualian yang tidak terkait → data yang terpotong sulit didiagnosis →

ubah kelelahan prematur menjadi kesalahan parse yang jelas.

• Mengklaim ruang tambahan selalu O(log n) → pohon yang miring memiliki tinggi n, dan tokenisasi

juga menggunakan ruang linier → pisahkan biaya keluaran, penyimpanan token, pohon, dan call-stack.

• Menyebut nilai preorder cukup untuk BST tanpa mendefinisikan duplikat → kunci yang sama dapat membuat

rekonstruksi ambigu → nyatakan kebijakan pengurutan dan duplikat sebelum menghapus penanda.

• Menggunakan kode rekursif untuk kedalaman yang tidak dipercaya tanpa batas → rantai panjang dapat menghabiskan stack →

gunakan stack eksplisit dan batas sumber daya.

• Membandingkan identitas objek setelah round trip → rekonstruksi membuat node baru → **bandingkan

nilai dan struktur.**

• Hanya menguji contoh seimbang → ambiguitas kiri/kanan dan risiko stack tetap tersembunyi → **sertakan

kasus kosong, satu sisi, duplikat, ekstrem, tidak valid, dan miring.**

Pertanyaan Lanjutan dan Respons

Lanjutan 1: Dapatkah binary search tree menghilangkan penanda null?

Sering ya. Dengan invariant BST yang ketat dan kunci unik, preorder dapat direkonstruksi dengan membawa batas bawah dan atas: nilai di dalam rentang saat ini menjadi milik subpohon tersebut, dan nilai pertama di luarnya menjadi milik ancestor. Jika duplikat diizinkan, kontrak harus menyatakan apakah nilai yang sama masuk ke kiri, kanan, atau dihitung di node. Tanpa kebijakan itu, format kompak bersifat ambigu. Masalah dasar pohon arbitrer tidak dapat menggunakan optimasi ini.

Lanjutan 2: Bagaimana cara mendukung nilai string arbitrer?

Koma dan # dapat muncul di dalam string, sehingga pemisahan delimiter tidak lagi self-delimiting. Satu opsi adalah length prefix seperti 5:hello, diikuti oleh tag node/null eksplisit. Opsi lain adalah pustaka serialisasi standar dengan skema. Escaping dapat bekerja, tetapi dekoder harus membedakan separator yang di-escape dari separator struktural dan menangani urutan escape yang tidak valid. Length prefix membuat aturan konsumsi lebih mudah dibuktikan.

Lanjutan 3: Apa yang berubah untuk pohon dengan jutaan node atau kedalaman ekstrem?

Hindari panggilan rekursif dan hindari memisahkan seluruh masukan jika memori puncak menjadi perhatian. Stream token melalui parser iteratif dengan stack eksplisit berisi slot anak, dan stream keluaran ke penulis alih-alih mengumpulkan semua token terlebih dahulu. Terapkan maksimum byte, token, node, panjang bilangan bulat, dan kedalaman sebelum mengalokasikan state yang tidak terbatas. Waktu tetap O(n), tetapi memori mengikuti stack aktif atau antrian ditambah kebijakan buffer keluaran.

Lanjutan 4: Bagaimana cara membuat versi format ini dalam sistem produksi?

Tambahkan identifier format dan versi di luar payload pohon, definisikan lebar bilangan bulat dan pengkodean teks, dan tentukan apakah field atau versi yang tidak dikenal gagal secara tertutup. Sertakan pemeriksaan integritas ketika korupsi harus dideteksi, tetapi jangan perlakukan checksum sebagai autentikasi. Rollout memerlukan kompatibilitas read-old/write-new dan fixture untuk setiap versi yang didukung. Untuk layanan lintas bahasa, format berbasis skema yang dikelola biasanya lebih aman daripada memperluas codec wawancara.

Lanjutan 5: Dapatkah serialisasi level-order dengan aman memangkas null yang tersisa di akhir?

Ya, jika dekoder mendefinisikan posisi yang dihilangkan setelah node nyata terakhir sebagai null dan serializer hanya memangkas rangkaian null terakhir. Serializer tidak boleh menghapus null internal karena itu mengubah penyelarasan anak dari node-node berikutnya. Kontrak round-trip dan aturan masukan tidak valid harus diuji setelah pemangkasan; "terlihat seperti array yang lebih pendek" bukan bukti kesetaraan.