Rekursi, Tree & Graph

Kenapa ini penting

Tree dan graph ada di mana-mana dalam pekerjaan front-end dan full-stack: DOM adalah tree, React component tree adalah tree, struktur folder adalah tree, dependency antar package di node_modules adalah graph, relasi follow di media sosial adalah graph, peta jalan di aplikasi ojek online adalah graph berbobot. Di interview, kategori ini menguji apakah kamu nyaman dengan rekursi dan bisa memilih antara DFS (telusuri sedalam mungkin) dan BFS (telusuri lapis demi lapis).

Analogi rekursi: boneka Matryoshka. Untuk menghitung jumlah boneka, kamu buka satu, lalu "hitung boneka di dalamnya" dengan cara yang sama, sampai bertemu boneka terkecil yang tidak bisa dibuka (base case). Analogi DFS vs BFS: mencari kunci di rumah. DFS = periksa satu ruangan sampai ke laci terdalam sebelum pindah ruangan. BFS = periksa permukaan semua ruangan di lantai 1 dulu, baru lantai 2.

Konsep inti

Rekursi: dua pertanyaan wajib

1. Base case: kapan berhenti? Untuk tree biasanya if (!node) return ....
2. Recursive case: bagaimana jawaban untuk node ini dibangun dari jawaban anak-anaknya?

Kalau kamu bisa menjawab dua pertanyaan itu dalam satu kalimat, kodenya biasanya 3-5 baris. Contoh maxDepth: "Depth of an empty tree is 0; otherwise it's 1 plus the larger depth of its children."

Peringatan JS: rekursi sangat dalam (misalnya puluhan ribu level) bisa menyebabkan RangeError: Maximum call stack size exceeded. Batas pastinya tergantung engine dan memori, jadi jangan hafalkan angka. Untuk tree miring atau grid besar, sebutkan bahwa versi iteratif dengan stack eksplisit lebih aman.

Binary tree dan traversal

Binary Search Tree (BST): untuk setiap node, semua nilai di subtree kiri lebih kecil dan semua nilai di subtree kanan lebih besar. Kata "semua" itu penting: mengecek hanya anak langsung adalah bug klasik.

Graph

Representasi yang paling praktis di JS adalah adjacency list: Map dari node ke array tetangga. Yang membedakan graph dari tree: graph bisa punya siklus, jadi kamu wajib menyimpan visited. Pilihan algoritma:

Grid (matriks 2D) adalah graph terselubung: tiap sel adalah node, tetangganya atas/bawah/kiri/kanan. Soal "Number of Islands" adalah soal graph yang menyamar sebagai soal matriks.

Contoh percakapan interview: memilih DFS atau BFS

Interviewer: "Given a grid of '1's for land and '0's for water, count the islands."

Candidate: "Are islands connected only horizontally and vertically, or diagonally too? And may I modify the grid?"

Interviewer: "Only four directions. Try not to modify the input."

Candidate: "Then I'll treat each land cell as a node with up to four neighbors. I scan the grid; whenever I find unvisited land, I increment the count and flood-fill the whole island with DFS so I don't count it again. Since I shouldn't modify the input, I'll either copy the grid or keep a visited set. It's O(rows times columns) time and space."

Interviewer: "What if the grid is huge, say a single island of millions of cells?"

Candidate: "Recursive DFS could overflow the call stack in JavaScript. I'd switch to an iterative DFS with an explicit stack, or BFS with a queue. The complexity stays the same; only the risk changes."

Jawaban terakhir menunjukkan pemahaman batasan bahasa yang kamu pakai. Ingat: ketika interviewer menambah skala, mereka biasanya sedang menguji apakah kamu tahu titik lemah solusimu sendiri.

Contoh kode

// Bangun binary tree dari array level-order (format LeetCode, null = kosong)
class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
function buildTree(arr) {
  if (!arr.length || arr[0] === null) return null;
  const root = new TreeNode(arr[0]); const queue = [root]; let i = 1;
  while (i < arr.length) {
    const node = queue.shift();
    if (arr[i] != null) { node.left = new TreeNode(arr[i]); queue.push(node.left); } i++;
    if (i < arr.length && arr[i] != null) { node.right = new TreeNode(arr[i]); queue.push(node.right); } i++;
  }
  return root;
}
const t = buildTree([4, 2, 7, 1, 3, 6, 9]);

// Traversal DFS rekursif
const preorder = n => n ? [n.val, ...preorder(n.left), ...preorder(n.right)] : [];
const inorder = n => n ? [...inorder(n.left), n.val, ...inorder(n.right)] : [];
const postorder = n => n ? [...postorder(n.left), ...postorder(n.right), n.val] : [];
console.log('pre', preorder(t).join(' '), '| in', inorder(t).join(' '), '| post', postorder(t).join(' '));
// → pre 4 2 1 3 7 6 9 | in 1 2 3 4 6 7 9 | post 1 3 2 6 9 7 4

// BFS level order
function levelOrder(root) {
  if (!root) return [];
  const result = []; let level = [root];
  while (level.length) {
    result.push(level.map(n => n.val));
    level = level.flatMap(n => [n.left, n.right].filter(Boolean));
  }
  return result;
}
console.log(JSON.stringify(levelOrder(t)), JSON.stringify(levelOrder(null)));
// → [[4],[2,7],[1,3,6,9]] []

// Max depth: base case + recursive case dalam satu baris
const maxDepth = n => n ? 1 + Math.max(maxDepth(n.left), maxDepth(n.right)) : 0;
console.log(maxDepth(t), maxDepth(buildTree([3, 9, 20, null, null, 15, 7])), maxDepth(null));
// → 3 3 0

// Validate BST: bawa batas bawah/atas, bukan hanya membandingkan dengan anak langsung
function isValidBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}
console.log(isValidBST(t), isValidBST(buildTree([5, 1, 4, null, null, 3, 6])), isValidBST(buildTree([5, 4, 6, null, null, 3, 7])));
// → true false false

// Graph: adjacency list + BFS jarak terpendek (tak berbobot)
function shortestPath(edges, start, goal) {
  const graph = new Map();
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, []); if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push(b); graph.get(b).push(a);
  }
  const dist = new Map([[start, 0]]); const queue = [start];   // dist sekaligus berfungsi sebagai visited
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i];
    if (node === goal) return dist.get(node);
    for (const nb of graph.get(node) ?? []) if (!dist.has(nb)) { dist.set(nb, dist.get(node) + 1); queue.push(nb); }
  }
  return -1;
}
const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D'], ['D', 'E']];
console.log(shortestPath(edges, 'A', 'E'), shortestPath(edges, 'A', 'A'), shortestPath(edges, 'A', 'Z'));
// → 3 0 -1

// Number of Islands: DFS di grid
function numIslands(grid) {
  const g = grid.map(row => [...row]);       // salin supaya input tidak rusak
  const R = g.length, C = g[0]?.length ?? 0; let count = 0;
  const sink = (r, c) => {
    if (r < 0 || c < 0 || r >= R || c >= C || g[r][c] !== '1') return;
    g[r][c] = '0';                            // tandai sudah dikunjungi
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (g[r][c] === '1') { count++; sink(r, c); }
  return count;
}
console.log(numIslands(['11110', '11010', '11000', '00000']), numIslands(['11000', '11000', '00100', '00011']), numIslands([]));
// → 1 3 0

Test case [5, 4, 6, null, null, 3, 7] untuk isValidBST sengaja menjebak: node 3 adalah anak kiri dari 6 (lokal benar, 3 < 6), tapi 3 berada di subtree kanan root 5, sehingga melanggar BST. Kode yang hanya membandingkan anak langsung akan menjawab true.

Kompleksitas: traversal dan maxDepth O(n) waktu, O(h) ruang call stack. shortestPath O(V + E). numIslands O(R·C) waktu; ruang rekursi terburuk O(R·C) kalau seluruh grid satu pulau.

Kesalahan umum

1. Lupa base case atau base case salah (misalnya if (!node.left)), menyebabkan error atau rekursi tak berujung. Cara benar: mulai dari if (!node) return ....
2. Validasi BST hanya ke anak langsung. Cara benar: bawa batas lo dan hi ke bawah.
3. Lupa visited di graph. Graph dengan siklus membuat BFS/DFS berputar selamanya. Cara benar: tandai saat memasukkan ke queue, bukan saat mengeluarkan, supaya node tidak masuk antrean dua kali.
4. Merusak input grid tanpa izin. Cara benar: tanyakan "Is it okay to modify the grid in place?" atau salin dulu.
5. Memakai DFS untuk jalur terpendek graph tak berbobot. DFS menemukan sebuah jalur, belum tentu yang terpendek. Cara benar: BFS.

Latihan

1. Mudah, invertTree(root): tukar anak kiri dan kanan di setiap node (cermin).
2. Sedang, Lowest Common Ancestor di BST: diberi nilai p dan q, kembalikan nilai leluhur bersama terdalam.
3. Menantang, Course Schedule: canFinish(n, prerequisites) dengan [course, pre] artinya harus ambil pre dulu. Kembalikan true kalau semua mata kuliah bisa diselesaikan (tidak ada siklus).

// 1. Rekursi: invert anak lalu tukar
function invertTree(n) { if (!n) return null; [n.left, n.right] = [invertTree(n.right), invertTree(n.left)]; return n; }
console.log(JSON.stringify(levelOrder(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9])))));
// → [[4],[7,2],[9,6,3,1]]

// 2. Manfaatkan sifat BST: kalau p dan q sama-sama lebih kecil, LCA ada di kiri, dan sebaliknya
function lcaBST(root, p, q) {
  let n = root;
  while (n) { if (p < n.val && q < n.val) n = n.left; else if (p > n.val && q > n.val) n = n.right; else return n.val; }
}
const bst = buildTree([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
console.log(lcaBST(bst, 2, 8), lcaBST(bst, 2, 4), lcaBST(bst, 3, 5));
// → 6 2 4

// 3. Kahn's algorithm: ambil terus mata kuliah tanpa prasyarat tersisa
function canFinish(n, prereq) {
  const indeg = new Array(n).fill(0), adj = Array.from({ length: n }, () => []);
  for (const [course, pre] of prereq) { adj[pre].push(course); indeg[course]++; }
  const queue = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
  let done = 0;
  for (let i = 0; i < queue.length; i++) { done++; for (const nx of adj[queue[i]]) if (--indeg[nx] === 0) queue.push(nx); }
  return done === n;   // kalau ada siklus, sebagian mata kuliah tidak pernah mencapai indegree 0
}
console.log(canFinish(2, [[1, 0]]), canFinish(2, [[1, 0], [0, 1]]), canFinish(4, [[1, 0], [2, 1], [3, 2]]));
// → true false true

Ringkasan

• Rekursi = base case + recursive case; sebutkan risiko stack overflow untuk input sangat dalam.
• Preorder/inorder/postorder adalah DFS; level order adalah BFS. Inorder di BST menghasilkan urutan terurut.
• Validasi BST dengan membawa batas min/max, bukan membandingkan anak langsung.
• Graph butuh visited; BFS untuk jalur terpendek tak berbobot, topological sort untuk dependensi.
• Grid adalah graph: tiap sel node, tetangga 4 arah.