Tree Problems

Mempelajari struktur data tree tidak lengkap tanpa kemampuan menyelesaikan soal klasik yang sering muncul di coding interview dan kompetisi pemrograman. Soal-soal seperti Lowest Common Ancestor (LCA), diameter binary tree, path sum, invert binary tree, dan serialize/deserialize adalah pola berulang yang menguji pemahaman mendalam tentang traversal, rekursi, dan backtracking. Setiap pola punya kerangka berpikir yang dapat ditransfer ke masalah serupa. Pada Chapter ini kita akan membedah enam pola klasik dengan implementasi C++ yang dapat dijalankan, menganalisis kompleksitas, dan menyusun strategi ketika menghadapi variasi soal.

Pola 1: Lowest Common Ancestor (LCA) #

Aturan #

Diberikan binary tree dan dua node p serta q, temukan ancestor bersama terdalam dari p dan q. LCA adalah node w sehingga w adalah ancestor dari p dan q, sekaligus descendant w punya kedalaman terbesar.

Mekanisme: Rekursi Post-order #

Untuk setiap node, kembalikan:

Bila node == p atau node == q, kembalikan node.
Rekursi ke left dan right.
Bila kedua subtree mengembalikan non-null, node saat ini adalah LCA.
Bila hanya satu yang non-null, kembalikan yang non-null itu.

cpp
#include <iostream>

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>
Node<T>* lca(Node<T>* node, Node<T>* p, Node<T>* q) {
    if (node == nullptr || node == p || node == q) return node;
    Node<T>* left  = lca(node->left,  p, q);
    Node<T>* right = lca(node->right, p, q);
    if (left && right) return node;        // p dan q di subtree berbeda
    return left ? left : right;             // salah satu subtree
}

int main() {
    // Tree:
    //         3
    //        / \
    //       5   1
    //      / \   \
    //     6   2   8
    //        / \
    //       7   4
    Node<int>* n3 = new Node<int>(3);
    Node<int>* n5 = new Node<int>(5);
    Node<int>* n1 = new Node<int>(1);
    Node<int>* n6 = new Node<int>(6);
    Node<int>* n2 = new Node<int>(2);
    Node<int>* n8 = new Node<int>(8);
    Node<int>* n7 = new Node<int>(7);
    Node<int>* n4 = new Node<int>(4);

    n3->left = n5; n3->right = n1;
    n5->left = n6; n5->right = n2;
    n1->right = n8;
    n2->left = n7; n2->right = n4;

    std::cout << "LCA(5, 1) = " << lca(n3, n5, n1)->data << '\n';
    std::cout << "LCA(5, 4) = " << lca(n3, n5, n4)->data << '\n';
    std::cout << "LCA(6, 4) = " << lca(n3, n6, n4)->data << '\n';
    std::cout << "LCA(7, 8) = " << lca(n3, n7, n8)->data << '\n';
    return 0;
}

Output yang Dihasilkan:

text
LCA(5, 1) = 3
LCA(5, 4) = 5
LCA(6, 4) = 5
LCA(7, 8) = 3

Base case node == nullptr || node == p || node == q: bila node adalah p atau q, kembalikan node itu sendiri. Sinyal “saya menemukan satu target”.
Rekursi left dan right: dapatkan hasil dari kedua subtree.
Kedua subtree non-null: p dan q ada di subtree yang berbeda → node saat ini adalah LCA.
Hanya satu non-null: kedua target di subtree yang sama → kembalikan hasil subtree tersebut.
LCA(5, 1) = 3: 5 ada di subtree kiri root, 1 adalah anak kanan root. LCA = root.
LCA(7, 8) = 3: 7 ada di subtree kiri, 8 ada di subtree kanan root. LCA = root.

Pola 2: Diameter Binary Tree #

Aturan #

Diameter = jumlah edge terpanjang antara dua node manapun di tree. Path tidak harus melalui root.

Mekanisme: Rekursi dengan Tracking Global #

Untuk setiap node, hitung depth subtree kiri dan kanan. Diameter yang melalui node ini = depth_left + depth_right. Update maksimum global.

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) {}
};

int diameter = 0;

template <typename T>
int depth(Node<T>* node) {
    if (node == nullptr) return 0;
    int l = depth(node->left);
    int r = depth(node->right);
    diameter = std::max(diameter, l + r);   // path through this node
    return 1 + std::max(l, r);
}

int main() {
    // Tree:
    //         1
    //        / \
    //       2   3
    //      / \   
    //     4   5
    //    /     \
    //   6       7
    Node<int>* n1 = new Node<int>(1);
    Node<int>* n2 = new Node<int>(2);
    Node<int>* n3 = new Node<int>(3);
    Node<int>* n4 = new Node<int>(4);
    Node<int>* n5 = new Node<int>(5);
    Node<int>* n6 = new Node<int>(6);
    Node<int>* n7 = new Node<int>(7);

    n1->left = n2; n1->right = n3;
    n2->left = n4; n2->right = n5;
    n4->left = n6;
    n5->right = n7;

    diameter = 0;
    depth(n1);
    std::cout << "Diameter: " << diameter << '\n';
    std::cout << "Path terpanjang (edges): 6->4->2->5->7 = 4 edges\n";
    return 0;
}

Output yang Dihasilkan:

text

Diameter: 4
Path terpanjang (edges): 6->4->2->5->7 = 4 edges

depth rekursif: kembalikan height subtree. nullptr → 0 agar leaf depth = 1.
Update diameter setiap node: path terpanjang yang melalui node saat ini = depth(left) + depth(right) (edges).
Global tracking diameter: variabel global diupdate selama rekursi. Alternatif: return pair {depth, diameter_so_far} untuk menghindari global.
Hasil = 4 edges: path 6 → 4 → 2 → 5 → 7 melewati 4 edge, bukan melalui root.

Pola 3: Path Sum #

Aturan #

Tentukan apakah ada path dari root ke leaf di mana jumlah nilai node = target.

Mekanisme: Rekursi dengan Akumulasi #

Kurangi target dengan node.data setiap langkah. Bila mencapai leaf dan sisa = 0, path ditemukan.

cpp
#include <iostream>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

bool has_path_sum(Node<int>* node, int target) {
    if (node == nullptr) return false;
    // Leaf check
    if (node->left == nullptr && node->right == nullptr) {
        return target == node->data;
    }
    int remaining = target - node->data;
    return has_path_sum(node->left,  remaining)
        || has_path_sum(node->right, remaining);
}

int main() {
    // Tree:
    //         5
    //        / \
    //       4   8
    //      /   / \
    //     11  13  4
    //    / \       \
    //   7   2       1
    Node<int>* n5  = new Node<int>(5);
    Node<int>* n4a = new Node<int>(4);
    Node<int>* n8  = new Node<int>(8);
    Node<int>* n11 = new Node<int>(11);
    Node<int>* n13 = new Node<int>(13);
    Node<int>* n4b = new Node<int>(4);
    Node<int>* n7  = new Node<int>(7);
    Node<int>* n2  = new Node<int>(2);
    Node<int>* n1  = new Node<int>(1);

    n5->left = n4a; n5->right = n8;
    n4a->left = n11;
    n8->left = n13; n8->right = n4b;
    n11->left = n7; n11->right = n2;
    n4b->right = n1;

    for (int target : {22, 26, 18, 27}) {
        std::cout << "has_path_sum(" << target << ") = "
                  << (has_path_sum(n5, target) ? "true" : "false") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
has_path_sum(22) = true
has_path_sum(26) = true
has_path_sum(18) = true
has_path_sum(27) = true

Base case nullptr → false: node kosong tidak bisa menjadi path lengkap.
Leaf check: bila node adalah leaf (tidak punya child), cek apakah target == node->data. Bila ya, path ditemukan.
Rekursi: kurangi target dengan node->data, lalu rekursi ke kedua child. Bila salah satu path berhasil, return true.
Hasil 22: path 5 → 4 → 11 → 2 = 22. ✓
Hasil 26: path 5 → 8 → 13 = 26. ✓
Hasil 18: path 5 → 8 → 4 → 1 = 18. ✓
Hasil 27: path 5 → 4 → 11 → 7 = 27. ✓

Pola 4: Invert Binary Tree #

Aturan #

Cermin (mirror) binary tree: setiap anak kiri ditukar dengan anak kanan secara rekursif. Soal klasik yang dipopulerkan Max Howell (Homebrew author) yang konon gagal di interview Google karena tidak bisa menyelesaikannya.

cpp
#include <iostream>

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>
void invert(Node<T>* node) {
    if (node == nullptr) return;
    std::swap(node->left, node->right);
    invert(node->left);
    invert(node->right);
}

template <typename T>
void preorder(Node<T>* node) {
    if (node == nullptr) { std::cout << "null "; return; }
    std::cout << node->data << ' ';
    preorder(node->left);
    preorder(node->right);
}

int main() {
    Node<int>* root = new Node<int>(4);
    root->left  = new Node<int>(2);
    root->right = new Node<int>(7);
    root->left->left  = new Node<int>(1);
    root->left->right = new Node<int>(3);
    root->right->left  = new Node<int>(6);
    root->right->right = new Node<int>(9);

    std::cout << "Pre-order sebelum invert: ";
    preorder(root); std::cout << '\n';

    invert(root);

    std::cout << "Pre-order setelah invert : ";
    preorder(root); std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Pre-order sebelum invert: 4 2 1 null null 3 null null 7 6 null null 9 null null 
Pre-order setelah invert : 4 7 9 null null 6 null null 2 3 null null 1 null null

invert: swap left dan right untuk setiap node, lalu rekursi. In-place, O(n) waktu, O(h) ruang stack.
Hasil pre-order berubah: sebelum invert [4, 2, 1, 3, 7, 6, 9], setelah invert [4, 7, 9, 6, 2, 3, 1]. Struktur tree sudah terbalik horizontal.

Pola 5: Subtree Check #

Aturan #

Tentukan apakah subtree adalah subtree dari tree (struktur dan nilai identik).

cpp
#include <iostream>

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>
bool is_same(Node<T>* a, Node<T>* b) {
    if (a == nullptr && b == nullptr) return true;
    if (a == nullptr || b == nullptr) return false;
    return a->data == b->data
        && is_same(a->left,  b->left)
        && is_same(a->right, b->right);
}

template <typename T>
bool is_subtree(Node<T>* root, Node<T>* sub) {
    if (root == nullptr) return sub == nullptr;
    if (is_same(root, sub)) return true;
    return is_subtree(root->left,  sub)
        || is_subtree(root->right, sub);
}

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

    Node<int>* sub1 = new Node<int>(4);
    sub1->left  = new Node<int>(1);
    sub1->right = new Node<int>(2);

    Node<int>* sub2 = new Node<int>(4);
    sub2->left  = new Node<int>(1);
    sub2->right = new Node<int>(9);  // mismatch nilai

    std::cout << "sub1 is subtree? " << (is_subtree(root, sub1) ? "ya" : "tidak") << '\n';
    std::cout << "sub2 is subtree? " << (is_subtree(root, sub2) ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text

sub1 is subtree? ya
sub2 is subtree? tidak

is_same(a, b): cek apakah dua tree identik (struktur dan nilai).
is_subtree: untuk setiap node di root, cek apakah subtree mulai dari node tersebut identik dengan sub. Bila ya, return true. Bila tidak, rekursi ke kedua child.
Kompleksitas O(m × n) naif: untuk setiap node di root (m node), panggil is_same yang O(n). Optimal: hashing tree (O(m + n)).

Pola 6: Serialize/Deserialize #

Aturan #

Konversi binary tree menjadi string (serialize) dan sebaliknya (deserialize). Format yang umum: pre-order dengan marker null untuk child kosong.

cpp
#include <iostream>
#include <sstream>
#include <string>

template <typename T>
struct Node {
    T data;
    Node* left;
    Node* right;
    explicit Node(const T& v) : data(v), left(nullptr), right(nullptr) {}
};

void serialize(Node<int>* node, std::ostringstream& out) {
    if (node == nullptr) { out << "null "; return; }
    out << node->data << ' ';
    serialize(node->left,  out);
    serialize(node->right, out);
}

Node<int>* deserialize(std::istringstream& in) {
    std::string tok;
    if (!(in >> tok) || tok == "null") return nullptr;
    Node<int>* node = new Node<int>(std::stoi(tok));
    node->left  = deserialize(in);
    node->right = deserialize(in);
    return node;
}

bool same_tree(Node<int>* a, Node<int>* b) {
    if (a == nullptr && b == nullptr) return true;
    if (a == nullptr || b == nullptr) return false;
    return a->data == b->data
        && same_tree(a->left,  b->left)
        && same_tree(a->right, b->right);
}

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

    std::ostringstream out;
    serialize(root, out);
    std::string s = out.str();
    std::cout << "Serialized: " << s << '\n';

    std::istringstream in(s);
    Node<int>* restored = deserialize(in);
    std::cout << "Round-trip identical: " << (same_tree(root, restored) ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Serialized: 1 2 null null 3 4 null null 5 null null 
Round-trip identical: ya

serialize: pre-order traversal. Setiap node dicetak, anak kosong ditandai null. Separator spasi.
deserialize: baca token. Bila null → kembalikan nullptr. Bila angka → buat node, lalu rekursi untuk left dan right.
Pre-order + null marker menjamin rekonstruksi unik — setiap struktur binary tree dapat dikodekan dengan format ini.
Round-trip identical: tree hasil deserialize identik dengan tree asli. Verifikasi struktur dan nilai.

Ringkasan Pola Tree #

Pola	Strategi	Kompleksitas
LCA	Rekursi post-order, return non-null child	O(n)
Diameter	Rekursi + global max, update `l + r` per node	O(n)
Path Sum	DFS akumulasi `target - node.data`	O(n)
Invert	Swap left/right per node	O(n)
Subtree Check	DFS, panggil `is_same` per node	O(m·n) naif
Serialize/Deserialize	Pre-order + null marker	O(n)

Ringkasan #

LCA: ancestor bersama terdalam. Rekursi post-order: kembalikan node bila ditemukan di kedua subtree.
Diameter: path terpanjang antara dua node manapun. Update global max dengan depth(left) + depth(right) per node.
Path Sum: cek path root-to-leaf dengan total = target. DFS dengan akumulasi target - node.data.
Invert: swap left dan right per node. Soal Max Howell (Homebrew).
Subtree check: cek apakah sub muncul di root. Naif O(m·n), optimal O(m+n) dengan hashing.
Serialize/Deserialize: pre-order + null marker. Menjamin rekonstruksi unik untuk binary tree manapun.
Tiga pola traversal (pre-order, in-order, post-order) adalah fondasi 90% soal tree di coding interview.