Tree traversal artinya mengunjungi semua node di sebuah tree, masing-masing sekali, dengan urutan tertentu. Di sini tree-nya binary tree: node paling atas disebut root, tiap node punya paling banyak dua anak (kiri dan kanan), dan node tanpa anak disebut leaf. Urutannya penting, karena tiap urutan cocok untuk pekerjaan yang berbeda.
🧪 Tebakan cepat: di binary search tree (BST), urutan mana yang mengeluarkan angka dari kecil ke besar: pre-order, in-order, atau post-order? Tebak dulu, jawabannya ada di bagian "In-order di BST: hasilnya terurut".
Satu pohon, tiga urutan
1 Pre-order 1, 2, 4, 5, 3, 6, 7
/ \ In-order 4, 2, 5, 1, 6, 3, 7
2 3 Post-order 4, 5, 2, 6, 7, 3, 1
/ \ / \
4 5 6 7
Ketiganya cuma beda di satu hal: kapan sebuah node dicatat dibanding subtree kiri dan kanannya. Subtree adalah satu anak beserta semua keturunannya, misalnya subtree kiri dari 1 berisi 2, 4, dan 5.
- Pre-order: node itu dulu, lalu subtree kiri, lalu subtree kanan. Makanya 1 keluar pertama.
- In-order: subtree kiri, lalu node itu, lalu subtree kanan. Makanya 1 ada di tengah.
- Post-order: subtree kiri, subtree kanan, node itu paling akhir. Makanya 1 keluar terakhir.
Aturan yang sama dipakai lagi di dalam tiap subtree. Begini jalannya in-order dari root:
| Langkah | Posisi | Yang terjadi | Hasil sejauh ini |
|---|---|---|---|
| 1 | 1 | punya anak kiri, turun ke 2 dulu | (kosong) |
| 2 | 2 | punya anak kiri, turun ke 4 dulu | (kosong) |
| 3 | 4 | leaf: catat 4 | 4 |
| 4 | 2 | kiri selesai: catat 2, lalu ke kanan (5) | 4, 2 |
| 5 | 5 | leaf: catat 5 | 4, 2, 5 |
| 6 | 1 | subtree kiri selesai: catat 1, lalu ke kanan (3) | 4, 2, 5, 1 |
Subtree kanan diproses dengan cara yang sama: 6, 3, 7. Ada juga level-order: per level dari atas, kiri ke kanan (1, 2, 3, 4, 5, 6, 7). Yang ini pakai queue, dan bakal ketemu lagi di lesson graph dengan nama BFS.
Menulisnya dengan rekursi
const node = (value, left = null, right = null) => ({ value, left, right });
const root = node(1, node(2, node(4), node(5)), node(3, node(6), node(7)));
function inorder(t, out = []) {
if (!t) return out; // node kosong: gak ada yang dicatat
inorder(t.left, out); // 1. subtree kiri
out.push(t.value); // 2. node ini
inorder(t.right, out); // 3. subtree kanan
return out;
}
console.log(inorder(root)); // [4, 2, 5, 1, 6, 3, 7]
node(...)bikin satu node: object berisivalue,left, danright. Anak yang gak ada diisinull.inordermemanggil dirinya sendiri untuk anak kiri dan kanan. Ini namanya rekursi: function yang memanggil dirinya untuk bagian yang lebih kecil.if (!t) return out;adalah base case, tempat rekursi berhenti: sampai di anak yangnull, gak ada yang dicatat.outadalah satu array yang dioper ke semua panggilan. Tiappushmenambah satu value ke situ.
Pindahkan out.push(t.value) ke atas dua panggilan, jadilah pre-order. Pindahkan ke bawah keduanya, jadilah post-order. Tiap node dikunjungi tepat sekali, jadi waktunya O(n): node-nya dua kali lipat, waktunya kira-kira dua kali lipat.
Di latihan, pohonnya sama tapi tanpa 6 dan 7, node-nya dibuat dengan new TreeNode(...), dan function-nya bernama inOrder. In-order pohon itu: 4, 2, 5, 1, 3. Cara lain yang juga benar: tiap panggilan mengembalikan array sendiri, lalu digabung pakai spread, [...inOrder(node.left), node.value, ...inOrder(node.right)], dengan [] untuk node kosong.
In-order di BST: hasilnya terurut
Di BST, semua isi subtree kiri lebih kecil dari node-nya, dan semua isi subtree kanan lebih besar. In-order selalu mengunjungi kiri, node, lalu kanan, jadi angkanya keluar dari kecil ke besar. Itu jawaban tebakannya. Contohnya pohon tadi diisi sebagai BST: 4 di root, 2 dan 6 di bawahnya, lalu 1, 3, 5, 7. In-order-nya 1, 2, 3, 4, 5, 6, 7.
⚠️ Jebakan yang sering ketemu
- Lupa base case. Tanpa
if (!node) return ..., function membacanull.leftdan langsung error. - Hasil rekursi gak dipakai. Kalau tiap panggilan bikin array baru, hasil
inOrder(node.left)harus ikut digabung. Memanggilnya tanpa memakai hasilnya bikin isi kiri hilang. - Gak mengembalikan array. Kode latihan memanggil
.join(',')pada hasilnya. Kalau function mengembalikanundefined, termasuk untuk node kosong, muncul TypeError.
TL;DR: Traversal mengunjungi tiap node sekali. Pre-order: node, kiri, kanan. In-order: kiri, node, kanan. Post-order: kiri, kanan, node. Di function rekursif, bedanya cuma posisi baris yang mencatat node, dan base case if (!node) menghentikan rekursinya. In-order di BST menghasilkan angka terurut. Level-order jalan per level dengan queue.
