Binary Tree

Binary tree adalah tree di mana setiap node memiliki paling banyak dua child: left child dan right child. Pembatasan ini membuat binary tree cocok untuk representasi data yang secara alami berpasangan kiri-kanan, seperti ekspresi matematika (a + b) * c atau keputusan ya/tidak pada decision tree. Lebih penting lagi, binary tree menjadi fondasi hampir semua struktur data tree lanjutan: BST, AVL, Red-Black, dan heap semuanya adalah binary tree dengan aturan tambahan. Pada Chapter ini kita akan melihat empat tipe binary tree (full, complete, perfect, skewed), mengimplementasikan node binary tree dengan struct Node { T data; Node* left; Node* right; }, dan menghitung properti penting seperti jumlah node dan height secara rekursif.

Struktur Node Binary Tree #

Setiap node pada binary tree menyimpan data dan dua pointer child. Konvensi C++:

cpp
template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;

    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

Pointer left dan right bernilai nullptr bila child tidak ada. Sebuah node boleh punya 0, 1, atau 2 child — tidak lebih.

Empat Tipe Binary Tree #

Mengklasifikasikan binary tree membantu kita memahami sifat-sifatnya:

Full Binary Tree (Strict Binary Tree) #

Setiap node memiliki 0 atau 2 child. Tidak ada node dengan hanya satu child.

flowchart TD A["A"] --> B["B"] A --> C["C"] B --> D["D"] B --> E["E"]

Complete Binary Tree #

Semua level terisi penuh kecuali mungkin level terakhir, dan level terakhir terisi dari kiri ke kanan tanpa celah. Heap selalu merupakan complete binary tree.

flowchart TD A["A"] --> B["B"] A --> C["C"] B --> D["D"] B --> E["E"] C --> F["F"]

Perfect Binary Tree #

Semua level terisi penuh. Jumlah node = 2^(h+1) - 1, di mana h adalah height tree.

flowchart TD A["A"] --> B["B"] A --> C["C"] B --> D["D"] B --> E["E"] C --> F["F"] C --> G["G"]

Skewed Binary Tree #

Setiap node punya paling banyak satu child, sehingga tree menyerupai linked list. Bisa left-skewed (semua anak kiri) atau right-skewed (semua anak kanan).

flowchart TD A["A"] --> B["B"] B --> C["C"] C --> D["D"]

Properti Penting Binary Tree #

Beberapa properti matematis yang sering muncul di soal:

Properti	Rumus	Catatan
Maksimum node pada level `k`	2^k	Level root = 0
Maksimum node pada tree height `h`	2^(h+1) − 1	Perfect binary tree
Minimum height dari `n` node	⌊log₂ n⌋	Complete binary tree
Jumlah leaf pada full binary tree	jumlah internal + 1	Rumus tak terduga
Jumlah maksimum leaf pada height `h`	2^h	Perfect binary tree

Implementasi: Membangun dan Menghitung Properti #

Berikut kode lengkap yang membangun sebuah binary tree contoh dan menghitung jumlah node, jumlah leaf, dan height:

cpp
#include <iostream>
#include <algorithm>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;

    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

template <typename T>
int count_nodes(const Node<T>* node) {
    if (node == nullptr) return 0;
    return 1 + count_nodes(node->left) + count_nodes(node->right);
}

template <typename T>
int count_leaves(const Node<T>* node) {
    if (node == nullptr) return 0;
    if (node->left == nullptr && node->right == nullptr) return 1;
    return count_leaves(node->left) + count_leaves(node->right);
}

template <typename T>
int height(const Node<T>* node) {
    if (node == nullptr) return -1;
    return 1 + std::max(height(node->left), height(node->right));
}

template <typename T>
bool is_full(const Node<T>* node) {
    if (node == nullptr) return true;
    bool has_left  = node->left  != nullptr;
    bool has_right = node->right != nullptr;
    if (has_left != has_right) return false;        // hanya 1 child → bukan full
    return is_full(node->left) && is_full(node->right);
}

template <typename T>
void destroy(Node<T>* node) {
    if (node == nullptr) return;
    destroy(node->left);
    destroy(node->right);
    delete node;
}

int main() {
    // Tree:
    //         1
    //        / \
    //       2   3
    //      / \
    //     4   5
    Node<int>* root = new Node<int>(1);
    root->left  = new Node<int>(2);
    root->right = new Node<int>(3);
    root->left->left  = new Node<int>(4);
    root->left->right = new Node<int>(5);

    std::cout << "Jumlah node  : " << count_nodes(root) << '\n';
    std::cout << "Jumlah leaf  : " << count_leaves(root) << '\n';
    std::cout << "Height       : " << height(root) << '\n';
    std::cout << "Is full tree : " << (is_full(root) ? "ya" : "tidak") << '\n';

    destroy(root);
    return 0;
}

Output yang Dihasilkan:

text
Jumlah node  : 5
Jumlah leaf  : 3
Height       : 2
Is full tree : ya

count_nodes: rekursif. Jumlah node = 1 (diri sendiri) + jumlah node di left subtree + jumlah node di right subtree. Base case nullptr → 0.
count_leaves: leaf terdeteksi ketika left == nullptr && right == nullptr. Bukan leaf → jumlahkan leaf dari kedua subtree.
height: base case nullptr → -1 agar leaf punya height 0. Rekursif: 1 + max(height(left), height(right)).
is_full: cek setiap node — bila punya tepat satu child (XOR antara has_left dan has_right), tree bukan full. Bila 0 atau 2 child, lanjut rekursi ke kedua subtree.
Hasil Is full tree : ya: node 1 dan 2 masing-masing punya 2 child, sedangkan node 3, 4, 5 punya 0 child. Tidak ada node yang punya tepat satu child — sesuai definisi full binary tree.

Array Representation Binary Tree #

Selain pointer, binary tree (khususnya complete binary tree) dapat direpresentasikan sebagai array. Untuk node pada indeks i:

Parent: (i - 1) / 2
Left child: 2*i + 1
Right child: 2*i + 2

Representasi array ini dipakai oleh binary heap karena heap selalu complete binary tree — tidak ada ruang array yang terbuang.

cpp
#include <iostream>
#include <vector>

int main() {
    // Heap array: complete binary tree
    //         10
    //        /  \
    //       20   30
    //      / \
    //    40   50
    std::vector<int> tree = {10, 20, 30, 40, 50};

    auto parent = [](int i) { return (i - 1) / 2; };
    auto left   = [](int i) { return 2 * i + 1; };
    auto right  = [](int i) { return 2 * i + 2; };

    std::cout << "root: " << tree[0] << '\n';
    std::cout << "left child of root: " << tree[left(0)] << '\n';
    std::cout << "right child of root: " << tree[right(0)] << '\n';
    std::cout << "parent of index 4: " << tree[parent(4)] << '\n';
    return 0;
}

Output yang Dihasilkan:

text
root: 10
left child of root: 20
right child of root: 30
parent of index 4: 20

tree = {10, 20, 30, 40, 50}: array berisi 5 elemen. Root tree[0] = 10. Anak kiri root = tree[1] = 20, anak kanan = tree[2] = 30.
parent(4) = (4-1)/2 = 1: indeks 4 adalah 50, parent-nya adalah tree[1] = 20. Sesuai diagram.
left(0) = 1, right(0) = 2: konversi indeks ke child memakai rumus matematika sederhana, tidak perlu pointer.

Ringkasan #

Binary tree: setiap node paling banyak punya 2 child (left, right).
Empat tipe utama: full (0 atau 2 child), complete (level terakhir terisi kiri-ke-kanan), perfect (semua level penuh), skewed (menyerupai linked list).
Skewed binary tree adalah kondisi patologis yang membuat operasi tree menjadi O(n).
Operasi dasar: count_nodes, count_leaves, height, dan is_full semuanya memakai pola rekursif post-order.
Complete binary tree dapat direpresentasikan sebagai array dengan rumus parent/child: parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2.