Tree Traversal adalah cara mengunjungi semua node di tree. Ada dua pendekatan utama:

DFS (Depth-First Search)

Masuk sedalam mungkin dulu sebelum mundur.

3 urutan DFS:

//       1
//      / \
//     2   3
//    / \
//   4   5

// In-order (Kiri → Root → Kanan): 4, 2, 5, 1, 3
function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}

// Pre-order (Root → Kiri → Kanan): 1, 2, 4, 5, 3
function preOrder(node) {
  if (!node) return;
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}

// Post-order (Kiri → Kanan → Root): 4, 5, 2, 3, 1
function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}

BFS (Breadth-First Search)

Kunjungi level per level dari atas ke bawah.

// Level-order: 1, 2, 3, 4, 5
function bfs(root) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

Kapan pakai yang mana?

• In-order → data terurut di BST
• Pre-order → copy/serialize tree
• Post-order → hapus tree, evaluasi ekspresi
• BFS → cari node terdekat, shortest path

🎭 Analogi sehari-hari: Cara kamu eksplor mall.

• DFS (pre-order): masuk lantai 1, jelajahi sampai pojok, baru naik lantai 2 — habis dulu satu cabang
• BFS: keliling semua toko di lantai 1 dulu, baru naik ke lantai 2 — semua tetangga dulu

💡 Cara hafal 3 DFS order: Posisi console.log(node) menentukan namanya:

• Sebelum kiri & kanan → Pre-order
• Antara kiri & kanan → In-order
• Setelah kiri & kanan → Post-order

Trik: ucapkan kapan node-nya "diproses" relatif ke child-nya.

⚠️ Jebakan umum:

• DFS rekursif = stack overflow untuk tree dalam (>10rb level). Convert ke iteratif pakai stack manual
• BFS pakai arr.shift() = O(n²). Pakai pointer-based queue atau library
• Lupa visited set = di graph (bukan tree) kunjungi node sama berkali-kali = infinite loop
• Pre-order ≠ Post-order untuk delete — jangan pakai pre-order untuk delete tree, child diakses setelah parent dihapus

🎯 DFS vs BFS kapan?

• Cari path apa saja yang mengarah ke target → DFS (lebih hemat memori)
• Cari path TERPENDEK → BFS (level-by-level menjamin shortest)
• Eksplorasi semua node tanpa peduli urutan → DFS lebih mudah ditulis
• Memori terbatas + tree lebar → DFS (BFS bisa kepenuhan queue)

🧪 Tebakan cepat: Tree 1 → (2,3) → (4,5). In-order? 4,2,5,1,3. BFS? 1,2,3,4,5.

TL;DR: DFS = sedalam dulu (3 varian: pre/in/post). BFS = selevel dulu (queue). In-order BST = sorted. BFS = shortest path.