Binary Tree adalah struktur hierarki di mana setiap node punya maksimal 2 child (kiri dan kanan).
Terminologi:
| Istilah | Penjelasan |
|---|---|
| Root | Node paling atas |
| Parent | Node yang punya child |
| Child | Node di bawah parent |
| Leaf | Node tanpa child |
| Height | Jarak terpanjang dari root ke leaf |
| Depth | Jarak dari root ke node tertentu |
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Bangun tree secara manual
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 1
// / \
// 2 3
// / \
// 4 5
Jenis-jenis Binary Tree:
- Full Binary Tree — setiap node punya 0 atau 2 child
- Complete Binary Tree — semua level terisi penuh kecuali level terakhir (diisi dari kiri)
- Perfect Binary Tree — semua level terisi penuh
- Balanced Binary Tree — perbedaan tinggi kiri dan kanan max 1
Kegunaan nyata:
- DOM (Document Object Model) — HTML adalah tree
- File system — folder dan file
- Expression tree — parsing ekspresi matematika
- Decision tree — machine learning
🎭 Analogi sehari-hari: Tree = silsilah keluarga. Kakek (root) punya 2 anak (left, right). Tiap anak punya max 2 anak juga. Cucu tanpa anak = leaf. Bedanya pohon di kebun: tree komputer digambar terbalik, root di atas.
💡 Mengapa "Binary"? Kenapa max 2 child, bukan lebih? Banyak struktur lain (n-ary tree, B-tree) punya >2 child. Binary tree dipakai karena gampang diimplementasi (cuma 2 pointer per node) dan rumus index di array bersih — node ke-i punya child di 2i+1 dan 2i+2. Ini foundation untuk Heap.
⚠️ Jebakan umum:
- Tree miring (skewed) = praktiknya jadi linked list. Operasi yang harusnya O(log n) jadi O(n)
- Lupa edge case
node === null= NPE/crash. Selalu cek di awal fungsi rekursif - Stack overflow di tree dalam = rekursi pakai call stack. Tree 100rb deep = crash. Pakai iteratif + manual stack
🎯 Jenis Binary Tree mana untuk apa?
- Full → expression parsing (operator pasti punya 2 operand)
- Complete → Heap (compact, bisa pakai array)
- Perfect → analisis teori
- Balanced → BST/AVL/Red-Black (jaga performa O(log n))
TL;DR: Binary Tree = struktur hierarki, max 2 child per node. Foundation untuk BST, Heap, dan parsing tree. Yang bikin powerful: balanced tree = O(log n).
