Wawancara Coding: Menemukan Lowest Common Ancestor dari Binary Tree

Masalah dan Cakupan

Diberikan sebuah binary tree sembarang dan dua node berbeda p dan q di dalamnya, kembalikan lowest common ancestor (LCA) keduanya. Sebuah node adalah leluhur dari dirinya sendiri. LCA adalah node terdalam yang subpohonnya memuat kedua target, jadi jika p adalah leluhur dari q, jawabannya adalah p itu sendiri.

Empat detail menentukan kontrak dasar: pohon ini bukan binary search tree; input mengidentifikasi objek node alih-alih nilainya; node-node terpisah dapat memiliki nilai yang sama; dan baik p maupun q dijamin ada di dalam pohon. Membandingkan nilai secara diam-diam melanggar kontrak tersebut. Menggunakan kembali rekursi dasar setelah menghapus jaminan keberadaan juga menghasilkan false positive yang halus.

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

Di sini, LCA(d, h) = b, LCA(b, h) = b, dan LCA(e, f) = a. Pertanyaan ini ditujukan bagi software engineer yang diharapkan memahami traversal pohon, semantik rekursif, dan kompleksitas. Kasus dasar meminta satu kueri. Kedalaman tak terbatas, target yang tidak ada, pointer induk (parent pointer), atau banyak kueri terhadap satu pohon statis adalah batasan lanjutan yang mengubah solusi terbaik.

Apa yang Sedang Dinilai oleh Pewawancara

Pengamatan berguna pertama mengubah kata "terendah" (lowest) menjadi struktur: jawabannya adalah node bersama terakhir pada jalur root-ke-p dan root-ke-q. Menyimpan kedua jalur adalah benar, tetapi tidak perlu. Penurunan yang lebih tajam meminta setiap subpohon untuk melaporkan salah satu dari tiga status: tidak ada target yang ditemukan, satu target ditemukan, atau titik di mana kedua target telah bertemu.

Jawaban yang kuat mendefinisikan nilai kembalian rekursif secara tepat. Untuk subpohon yang berakar di node, fungsi mengembalikan:

• null ketika subpohon tidak memuat p maupun q;
• p atau q ketika satu target yang ditemukan harus dipropagasi ke atas;
• node lain ketika node tersebut sudah menjadi LCA di dalam subpohon ini.

Ketika kedua hasil rekursif bernilai non-null, target-target tersebut bertemu melalui sisi yang berbeda dari node saat ini, sehingga node saat ini adalah jawabannya. Ketika hanya satu sisi yang non-null, hasilnya dipropagasi. Kasus dasar segera kembali ketika node saat ini adalah target karena keberadaannya dijamin: jika target lainnya berada di bawahnya, node ini adalah LCA; jika tidak, node ini harus melaporkan satu target ke leluhurnya.

Jebakan kontrak sangat penting. Jika q tidak ada, algoritma dasar dapat mengembalikan p; ini tidak serta-merta membuktikan bahwa kedua target ada. Setelah jaminan tersebut dihapus, hasil rekursif memerlukan hitungan kecocokan (match count). Untuk pohon dengan n node dan tinggi h, satu kueri mengunjungi setiap node pada kasus terburuk, sehingga waktu adalah O(n) dan tumpukan rekursif adalah O(h). Pada pohon yang condong (skewed tree), h = n, dan call stack bisa menjadi titik kegagalan alih-alih beban kerja algoritmik.

Pertanyaan untuk Diklarifikasi Terlebih Dahulu

• Apakah input berupa referensi node atau nilai? Referensi memungkinkan adanya nilai duplikat, jadi bandingkan dengan node === p. Pencarian nilai hanya valid jika keunikan nilai adalah bagian dari kontrak.
• Apakah kedua target dijamin ada dan berbeda? Rekursi dasar bergantung pada keberadaan target. Jika salah satu bisa tidak ada, kembalikan juga match count. Jika p === q diperbolehkan, tentukan apakah menemukan objek tersebut sekali sudah cukup.
• Apakah ini binary tree sembarang atau binary search tree? Pohon sembarang membutuhkan pencarian struktural. BST dapat mengikuti urutan kunci ke satu jalur, tetapi kunci duplikat dan identitas referensi dapat membatalkan jalan pintas tersebut.
• Berapa jumlah maksimum node dan tingginya? Pohon yang seimbang memiliki kedalaman rekursi O(log n). Pohon rantai 100.000 node memerlukan stack eksplisit dan parent map untuk menghindari runtime stack overflow.
• Berapa banyak kueri yang menargetkan pohon statis yang sama? Kueri tunggal lebih cocok dengan DFS langsung. Banyak kueri dapat membenarkan pra-perhitungan kedalaman dan leluhur ke-2^k untuk kueri O(log n).
• Apakah node sudah memiliki pointer induk? Jika ya, root tidak perlu dilintasi. Samakan kedalaman dan telusuri ke atas bersama-sama, atau catat satu rantai leluhur dan temukan persimpangan pertamanya.

Kerangka Jawaban 30 Detik

"Pertama, saya akan mengonfirmasi bahwa ini adalah binary tree sembarang dan bahwa p serta q adalah referensi node yang dijamin ada, sehingga nilai duplikat tidak memengaruhi identitas. Fungsi rekursif saya mengembalikan target atau LCA yang ditemukan dalam subpohon. Node null mengembalikan null, dan node yang sama dengan p atau q mengembalikan dirinya sendiri. Setelah mencari di kedua anak, dua hasil non-null berarti target bertemu di node saat ini; jika tidak, saya mempropagasi satu hasil yang non-null. Setiap node dikunjungi paling banyak satu kali, menghasilkan waktu kasus terburuk O(n) dan ruang tumpukan O(h). Saya akan menguji cabang yang terpisah, target yang merupakan leluhur, nilai duplikat, dan pohon condong. Jika target mungkin tidak ada, saya menambahkan match count; jika tinggi pohon tidak terbatas, saya menggunakan stack eksplisit untuk membangun tautan induk."

Solusi Langkah demi Langkah

Langkah 1: Tetapkan Baseline Jalur yang Benar

Pendekatan paling langsung menemukan jalur root-ke-p dan root-ke-q, membandingkannya dari root, dan mengembalikan node bersama terakhir mereka. Ini menjelaskan definisinya dengan rapi dan secara alami memvalidasi bahwa kedua target ada. Dua lintasan DFS tetap memerlukan waktu O(n), sementara jalur dan rekursi menggunakan ruang O(h). Implementasi yang menyimpan setiap node yang dijelajahi dapat membengkak menjadi ruang O(n).

Redundansinya adalah bahwa kedua pencarian melintasi prefiks bersama yang besar. Satu-satunya informasi yang dibutuhkan adalah apa yang dilaporkan subpohon ke induknya, sehingga kedua jalur tersebut dapat dikompresi menjadi satu traversal postorder.

Langkah 2: Definisikan Nilai Kembalian dan Lintasi Sekali

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

Kode ini membandingkan identitas objek dan tidak pernah membaca value, sehingga nilai yang sama pada node yang terpisah tetap aman. Postorder sangat penting: node saat ini membutuhkan laporan dari kedua anaknya sebelum memutuskan apakah ia merupakan titik pertemuan pertama.

Langkah 3: Buktikan dengan Invarian

Perhatikan subpohon sembarang yang berakar di node, dan asumsikan kedua panggilan rekursif memenuhi definisi nilai kembalian.

1. Jika node bernilai null, subpohon tidak memuat target apa pun, jadi null adalah benar.
2. Jika node adalah p atau q, kembalikan node. Karena kedua target dijamin ada, target ini adalah LCA karena ia memuat target lainnya, atau ia harus melaporkan satu target ke leluhur.
3. Jika kedua hasil anak bernilai non-null, masing-masing sisi melaporkan sebuah target. Tidak ada node yang lebih dalam yang dimiliki oleh kedua sisi, jadi node adalah leluhur bersama terdalam.
4. Jika tepat satu sisi bernilai non-null, node saat ini tidak menciptakan titik pertemuan baru. Target atau LCA yang sudah lengkap dari sisi tersebut adalah satu-satunya hasil valid untuk dipropagasi. Jika keduanya null, kembalikan null.

Berdasarkan induksi struktural, hasil yang dikembalikan di root adalah LCA dari seluruh pohon. Pembuktian ini juga mencakup kasus leluhur yang mudah terlewatkan: ketika p adalah leluhur dari q, mencapai p akan mengembalikannya tanpa mengharuskan q dikembalikan dari bawah untuk kedua kalinya.

Langkah 4: Nyatakan Biaya Waktu dan Ruang yang Sebenarnya

Pada kasus terburuk, fungsi mengunjungi semua n node dan melakukan operasi konstan pada masing-masing node, sehingga waktu adalah O(n). Menemukan target lebih awal dapat melewati sebagian pohon, tetapi kasus terbaik bukanlah batas kasus terburuk.

Ruang bantu (auxiliary space) adalah O(h) untuk rekursi. Pada pohon yang seimbang, h = O(log n); pada pohon yang sepenuhnya condong, h = n. Referensi node yang dikembalikan tidak dihitung sebagai penyimpanan bantu. Menyebut solusi ini menggunakan ruang O(1) berarti mengabaikan call stack.

Langkah 5: Ubah Kontrak Saat Target Mungkin Hilang

Tanpa jaminan keberadaan, fungsi dasar dapat memberikan hasil yang keliru: jika hanya p yang ada di pohon, fungsi akan mempropagasi p hingga ke root. Versi yang aman membedakan node kandidat dari jumlah target yang benar-benar ditemukan.

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

Versi ini masih mengasumsikan p !== q. Jika referensi yang sama dapat diberikan dua kali, tentukan kontraknya terlebih dahulu: menemukan node tersebut sekali harus mengembalikannya alih-alih terus mewajibkan matches === 2. Perubahan batasan harus mendahului perubahan kode.

Langkah 6: Gunakan Stack Eksplisit dan Parent Map untuk Pohon yang Dalam

Ketika tinggi pohon dapat mendekati 100.000, ruang rekursi asimtotik tidak berubah, tetapi call stack runtime dapat mengalami overflow terlebih dahulu. Lintasi dengan stack eksplisit dan catat parent.get(child) = node hingga p dan q ada di dalam map. Masukkan setiap leluhur dari p ke dalam sebuah set, lalu telusuri ke atas dari q; anggota set pertama yang ditemui adalah LCA.

Alternatif ini tetap membutuhkan waktu O(n) dan menggunakan ruang eksplisit O(n). Ini mungkin menggunakan lebih banyak memori heap daripada rekursi, tetapi memindahkan sumber daya dari call stack yang kecil ke struktur data yang terkontrol. Untuk satu kueri pada pohon dengan batas tinggi yang wajar, versi rekursif lebih pendek dan lebih mudah dibuktikan, sehingga parent map sebaiknya tidak dijadikan pilihan default otomatis.

Langkah 7: Validasi Semantik dengan Kasus Uji Ekstrem (Adversarial Cases)

Minimal, cakup matriks ini:

Di luar contoh tetap, buat pohon-pohon kecil secara acak dan bandingkan hasil satu lintasan dengan baseline jalur berdasarkan identitas objek. Karena metode baseline dan metode yang dioptimalkan menggunakan pendekatan berbeda, pemeriksaan diferensial ini menangkap lebih banyak kecacatan daripada hanya beberapa asersi yang dipilih secara manual.

Contoh Jawaban Berkualitas Tinggi

"Pertama, saya akan mengunci kontraknya: ini adalah binary tree sembarang, p dan q adalah referensi node berbeda yang dijamin ada, dan nilainya boleh berulang. Oleh karena itu kode saya membandingkan referensi, bukan nilai.

Saya menggunakan satu kali postorder DFS. Untuk sebuah subpohon, fungsi mengembalikan null, satu target yang ditemukan, atau LCA yang sudah ditemukan sebelumnya. Node null mengembalikan null, dan node saat ini yang sama dengan salah satu target akan mengembalikan dirinya sendiri. Setelah melakukan rekursi ke kedua anak, dua hasil non-null berarti target pertama kali bertemu di node saat ini, jadi saya mengembalikannya. Jika hanya satu sisi yang non-null, saya mempropagasi hasil tersebut.

Kebenaran algoritma ini mengikuti invarian kembalian tersebut. Ketika target berada di subpohon anak yang berbeda, tidak ada node yang lebih dalam yang dapat memuat keduanya. Ketika satu target adalah leluhur dari yang lain, mengembalikan target leluhur tersebut secara langsung sesuai dengan definisi. Kasus terburuk mengunjungi setiap node satu kali dengan waktu O(n), dengan ruang tumpukan rekursif O(h); pohon yang condong membuat kedalaman tumpukan menjadi O(n).

Saya akan menguji cabang yang berlawanan, target yang merupakan leluhur, satu subpohon yang dalam, dan nilai duplikat. Jika target tidak dijamin ada, fungsi ini dapat mengembalikan satu target yang ada tersebut, jadi saya juga akan mengembalikan match count dan hanya menerima kandidat setelah menemukan keduanya. Jika pohonnya bisa sangat dalam, saya akan menggunakan stack eksplisit dan parent map untuk menghindari overflow pada call stack."

Kesalahan Umum

• Memperlakukan pohon sebagai BST dan memilih sisi berdasarkan nilai → binary tree sembarang tidak memiliki pengurutan kunci, dan nilai duplikat tidak mengidentifikasi node → cari berdasarkan struktur dan bandingkan referensi node.
• Mengembalikan node saat ini ketika salah satu anak bernilai non-null → satu target di satu sisi akan dipromosikan hingga ke root → kembalikan node saat ini hanya jika kedua sisi bernilai non-null; jika tidak, propagasikan hasil yang non-null.
• Mengasumsikan p harus berada tepat di bawah jawabannya → sebuah node adalah leluhur dari dirinya sendiri, jadi p bisa menjadi jawabannya → jadikan identitas node saat ini sebagai kasus dasar.
• Menggunakan kembali algoritma dasar ketika target bisa tidak ada → menemukan satu target tetap menghasilkan nilai non-null → kembalikan match count dan nyatakan berhasil hanya setelah menemukan keduanya.
• Mengklaim ruang bantu O(1) → frame rekursif bertambah seiring tinggi pohon dan mencapai O(n) pada pohon rantai → laporkan O(h) dan gunakan stack eksplisit jika kedalaman tidak terbatas.
• Melakukan pra-perhitungan binary lifting untuk satu kueri → kode dan penyimpanan O(n log n) tidak teramortisasi → gunakan satu DFS untuk satu kueri dan lakukan prapemrosesan hanya untuk banyak kueri.
• Hanya menguji dua daun di sisi yang berlawanan → bug terkait leluhur, nilai duplikat, target yang hilang, dan kedalaman tetap tersembunyi → susun pengujian di sekitar batasan kontrak.

Pertanyaan Lanjutan

Bagaimana jika p atau q mungkin tidak ada di dalam pohon?

Kembalikan node kandidat dan match count dari rekursi. Dengan target yang berbeda, hitungannya adalah 0, 1, atau 2. Kembalikan kandidat LCA hanya jika hasil root memiliki hitungan 2; jika tidak, kembalikan null. Menjalankan algoritma dasar dan hanya memeriksa apakah hasilnya non-null tidaklah cukup karena satu target yang ada itu sendiri bernilai non-null.

Bagaimana jika pohon memiliki 100.000 node dan mungkin sepenuhnya condong?

Gunakan stack eksplisit untuk membangun parent map. Setelah kedua target ditemukan, simpan leluhur p dalam sebuah set dan ikuti rantai induk q ke persimpangan pertama. Ini membutuhkan waktu O(n) dan ruang heap O(n), tetapi tidak menghabiskan 100.000 call frame bahasa. Jika ruang heap juga terbatas, klarifikasi apakah pointer induk atau antarmuka traversal terkontrol tersedia daripada berasumsi bahwa rekursi aman.

Bagaimana jika pohon statis yang sama harus menjawab satu juta kueri LCA?

DFS dengan O(n) per kueri tidak lagi memadai. Lakukan pra-perhitungan kedalaman setiap node dan leluhur ke-2^k-nya dalam waktu dan ruang O(n log n). Untuk setiap kueri, naikkan node yang lebih dalam ke kedalaman yang sama, lalu naikkan keduanya dari k terbesar ke bawah, menghasilkan waktu O(log n) per kueri. Pada volume kueri yang lebih besar lagi, Euler tour ditambah RMQ mungkin layak dievaluasi; frekuensi pembaruan, memori, dan persyaratan latensi menentukan skema prapemrosesan mana yang sesuai.

Bagaimana jika setiap node sudah memiliki pointer induk?

Tidak perlu melakukan traversal dari root. Hitung kedua kedalaman, naikkan node yang lebih dalam sampai kedalamannya cocok, lalu gerakkan keduanya ke atas sampai nilainya sama. Ini membutuhkan waktu O(h) dan ruang ekstra O(1). Cara lainnya, simpan semua leluhur p dan telusuri ke atas dari q; itu lebih sederhana tetapi menggunakan set O(h).

Bagaimana solusi berubah untuk binary search tree?

Dengan kunci unik dan kontrak yang menemukan target berdasarkan kunci, belok ke kiri ketika kedua kunci target lebih kecil, ke kanan ketika keduanya lebih besar, dan selain itu kembalikan titik pemisah saat ini atau target. Ini membutuhkan waktu O(h) dan ruang iteratif O(1). Jika nilai boleh berulang atau input tetap mengidentifikasi target berdasarkan referensi, tentukan penempatan kunci duplikat dan semantik pencarian terlebih dahulu; dua nilai saja tidak dapat secara aman menggantikan algoritma binary tree sembarang.