Binary Tree — Struktur Data

Binary Tree adalah struktur hierarki di mana setiap node punya maksimal 2 child (kiri dan kanan). Terminologi: Istilah Penjelasan Root Node paling atas Parent…

Tree (pohon) adalah struktur data yang bercabang: ada satu node di puncak, dan tiap node bisa punya anak. Binary tree adalah tree yang tiap node-nya punya paling banyak dua anak: anak kiri (left) dan anak kanan (right). Mirip bagan silsilah keluarga yang leluhurnya digambar di atas, hanya saja tiap orang paling banyak punya dua anak.

🧪 Tebakan cepat: di latihan nanti, function countNodes memanggil countNodes lagi di dalam dirinya sendiri. Kenapa itu gak jalan selamanya? Tebak dulu, jawabannya ada di bagian "Function yang memanggil dirinya sendiri".

Root, child, dan leaf

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, new TreeNode(6), new TreeNode(7))
);

//         1
//       /   \
//      2     3
//     / \   / \
//    4   5 6   7

console.log(root.value);            // 1
console.log(root.left.value);       // 2
console.log(root.left.right.value); // 5
console.log(root.left.left.left);   // null

Binary tree gak punya aturan soal nilai: angka berapa pun boleh ada di mana pun, yang dibatasi cuma jumlah anaknya. Pohon yang punya aturan "kiri lebih kecil, kanan lebih besar" namanya binary search tree, materi berikutnya.

Tinggi pohon

Tinggi (height) adalah jumlah langkah dari root ke leaf yang paling jauh. Pohon di atas punya 3 level (1, lalu 2 dan 3, lalu 4 sampai 7), dan tingginya 2, karena dari 1 ke 4 cuma dua langkah.

Tiap level muat dua kali lipat level di atasnya: 1, 2, 4, 8, dan seterusnya. Jadi pohon setinggi h punya h + 1 level, dan paling banyak menampung 2^(h+1) - 1 node (2 pangkat h+1, dikurangi 1):

Tinggi Jumlah level Node paling banyak
0 1 1
1 2 1 + 2 = 3
2 3 1 + 2 + 4 = 7
3 4 1 + 2 + 4 + 8 = 15

Pohon yang seimbang (balanced) tumbuh melebar, jadi 1.000 node cukup sekitar 10 level. Pohon yang miring, tiap node cuma punya satu anak, sebenarnya cuma linked list: 1.000 node jadi 1.000 level. Makin tinggi pohonnya, makin jauh jalan dari root ke bawah.

Hati-hati, ada cara hitung kedua: jumlah node di jalur terpanjang, yang sama dengan jumlah level. maxDepth di latihan memakai cara ini: pohon di atas 3, satu node saja 1, pohon kosong 0.

Function yang memanggil dirinya sendiri

Anak kiri dan anak kanan masing-masing adalah root dari pohon yang lebih kecil. Jadi function untuk pohon bisa bekerja begini: urus node ini, lalu panggil dirinya sendiri untuk pohon kiri dan pohon kanan. Cara ini disebut rekursi.

function jumlahNilai(node) {
  if (node === null) return 0;
  return node.value + jumlahNilai(node.left) + jumlahNilai(node.right);
}

const kecil = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(jumlahNilai(kecil)); // 6
console.log(jumlahNilai(null));  // 0
Panggilan Yang terjadi Hasilnya
node 2 2 + kiri null (0) + kanan null (0) 2
node 3 3 + 0 + 0 3
node 1 1 + hasil kiri (2) + hasil kanan (3) 6

Node 1 menunggu jawaban kedua anaknya dulu, baru menjumlahkan. Baris if (node === null) return 0 adalah tempat berhenti: tiap panggilan turun ke pohon yang lebih kecil, sampai akhirnya ketemu null, yang langsung menjawab 0 tanpa memanggil lagi. Itu jawaban tebakan tadi.

Pola yang sama dipakai di latihan:

⚠️ Jebakan yang sering ketemu

TL;DR: Binary tree: tiap node punya value, left dan right, paling banyak dua anak, tanpa aturan soal nilai. Root di puncak, leaf gak punya anak. Tinggi adalah jumlah langkah dari root ke leaf terjauh, dan pohon setinggi h muat paling banyak 2^(h+1) - 1 node. Pohon seimbang pendek, pohon miring sepanjang linked list. Function pohon biasanya rekursif: jawab 0 untuk null, lalu gabungkan node ini dengan hasil dari kiri dan kanan.

Yang akan kamu pelajari