Tree Traversal

Membangun binary tree hanyalah setengah pekerjaan; kita juga harus dapat mengunjungi setiap node secara sistematis. Bayangkan ingin mencetak semua nilai dalam BST secara terurut, atau mengevaluasi expression tree (a + b) * c yang memerlukan anak dievaluasi sebelum parent. Tanpa urutan kunjungan yang terdefinisi, kita tidak bisa menjawab pertanyaan dasar seperti “apakah node X ada di tree?” atau “apa representasi string dari tree ini?”. Pada Chapter ini kita akan mempelajari empat strategi traversal dasar: tiga strategi DFS (depth-first search) — pre-order, in-order, post-order — dan satu strategi BFS (breadth-first search) — level-order. Kita akan melihat implementasi rekursif dan iteratif, serta kapan masing-masing cocok dipakai.

Tiga Strategi DFS: Pre-order, In-order, Post-order #

Pada binary tree, setiap node memiliki tiga “titik kunjungan” yang mungkin: sebelum mengunjungi left subtree, di antara left dan right subtree, dan sesudah mengunjungi kedua subtree. Memilih titik kunjungan menentukan jenis DFS:

Traversal	Urutan Kunjungan	Sifat Khas
Pre-order	Node → Left → Right	Root pertama; untuk serialize tree
In-order	Left → Node → Right	BST menghasilkan urutan terurut
Post-order	Left → Right → Node	Root terakhir; untuk hapus tree, evaluasi expression

Visualisasi Traversal #

Pada tree contoh berikut, kita telusuri urutan kunjungan tiap strategi:

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

Pre-order: F, B, A, D, C, E, G, I, H (root, lalu subtree kiri, lalu subtree kanan).
In-order: A, B, C, D, E, F, G, H, I (kiri, root, kanan). Untuk BST, ini urutan terurut.
Post-order: A, C, E, D, B, H, I, G, F (kiri, kanan, root). Root selalu terakhir.

Implementasi Rekursif #

Versi rekursif paling ringkas karena pola tree bersifat alami rekursif:

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 preorder(const Node<T>* n) {
    if (n == nullptr) return;
    std::cout << n->data << ' ';
    preorder(n->left);
    preorder(n->right);
}

template <typename T>
void inorder(const Node<T>* n) {
    if (n == nullptr) return;
    inorder(n->left);
    std::cout << n->data << ' ';
    inorder(n->right);
}

template <typename T>
void postorder(const Node<T>* n) {
    if (n == nullptr) return;
    postorder(n->left);
    postorder(n->right);
    std::cout << n->data << ' ';
}

int main() {
    // Tree:
    //       F
    //      / \
    //     B   G
    //    / \   \
    //   A   D   I
    //      / \  /
    //     C  E H
    Node<char>* f = new Node<char>('F');
    Node<char>* b = new Node<char>('B');
    Node<char>* g = new Node<char>('G');
    Node<char>* a = new Node<char>('A');
    Node<char>* d = new Node<char>('D');
    Node<char>* i = new Node<char>('I');
    Node<char>* c = new Node<char>('C');
    Node<char>* e = new Node<char>('E');
    Node<char>* h = new Node<char>('H');

    f->left = b;  f->right = g;
    b->left = a;  b->right = d;
    d->left = c;  d->right = e;
    g->right = i;
    i->left = h;

    std::cout << "Pre-order  : ";
    preorder(f);  std::cout << '\n';
    std::cout << "In-order   : ";
    inorder(f);   std::cout << '\n';
    std::cout << "Post-order : ";
    postorder(f); std::cout << '\n';

    // Cleanup
    auto destroy = [](auto& self, Node<char>* n) -> void {
        if (!n) return;
        self(self, n->left);
        self(self, n->right);
        delete n;
    };
    destroy(destroy, f);
    return 0;
}

Output yang Dihasilkan:

text
Pre-order  : F B A D C E G I H 
In-order   : A B C D E F G H I 
Post-order : A C E D B H I G F 

preorder: cetak node sebelum mengunjungi subtree. Karena root dicetak pertama, traversal ini cocok untuk serialize tree ke bentuk linear (root, lalu child kiri, lalu child kanan).
inorder: cetak node di antara left dan right. Pada BST, traversal in-order menghasilkan urutan terurut ascending — ini sifat khas yang dipakai untuk verifikasi BST.
postorder: cetak node sesudah kedua subtree. Root selalu dicetak terakhir. Cocok untuk hapus tree (child dihapus dulu sebelum parent) dan evaluasi expression tree (subtree dievaluasi dulu sebelum parent diaplikasikan operator).
Hasil sesuai ekspektasi: in-order A B C D E F G H I terurut abjad karena tree di atas adalah BST valid (left < node < right).

Implementasi Iteratif dengan Stack #

Versi rekursif memakai call stack bawaan compiler. Versi iteratif memakai std::stack secara eksplisit. Beberapa interview meminta versi iteratif untuk menguji pemahaman call stack.

cpp
#include <iostream>
#include <stack>

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 preorder_iter(const Node<T>* root) {
    if (root == nullptr) return;
    std::stack<const Node<T>*> st;
    st.push(root);
    while (!st.empty()) {
        const Node<T>* n = st.top(); st.pop();
        std::cout << n->data << ' ';
        if (n->right) st.push(n->right);   // right didorong dulu agar left diproses lebih dulu
        if (n->left)  st.push(n->left);
    }
}

template <typename T>
void inorder_iter(const Node<T>* root) {
    std::stack<const Node<T>*> st;
    const Node<T>* cur = root;
    while (cur != nullptr || !st.empty()) {
        while (cur != nullptr) {
            st.push(cur);
            cur = cur->left;                // dorong semua kiri
        }
        cur = st.top(); st.pop();
        std::cout << cur->data << ' ';
        cur = cur->right;
    }
}

int main() {
    // Tree yang sama dengan contoh rekursif
    Node<char>* f = new Node<char>('F');
    Node<char>* b = new Node<char>('B');
    Node<char>* g = new Node<char>('G');
    Node<char>* a = new Node<char>('A');
    Node<char>* d = new Node<char>('D');
    Node<char>* i = new Node<char>('I');
    Node<char>* c = new Node<char>('C');
    Node<char>* e = new Node<char>('E');
    Node<char>* h = new Node<char>('H');

    f->left = b;  f->right = g;
    b->left = a;  b->right = d;
    d->left = c;  d->right = e;
    g->right = i;
    i->left = h;

    std::cout << "Pre-order iteratif : ";
    preorder_iter(f); std::cout << '\n';
    std::cout << "In-order iteratif  : ";
    inorder_iter(f);  std::cout << '\n';

    // Cleanup sederhana — abaikan leak untuk demo singkat
    return 0;
}

Output yang Dihasilkan:

text

Pre-order iteratif : F B A D C E G I H 
In-order iteratif  : A B C D E F G H I

preorder_iter: dorong root ke stack, lalu loop: pop, cetak, dorong right lalu left. Stack LIFO menyebabkan left diproses lebih dulu — sesuai urutan pre-order.
inorder_iter: pertama dorong seluruh jalur kiri paling dalam (cur = cur->left). Setelah tidak bisa lagi, pop, cetak, lalu pindah ke right subtree. Pola ini meniru call stack rekursif.
Urutan iteratif = rekursif: keduanya menghasilkan urutan yang sama persis — iteratif hanyalah simulasi eksplisit dari call stack.

Level-Order Traversal (BFS) dengan Queue #

Level-order mengunjungi node per level, dari root ke leaf. Strategi ini memerlukan queue FIFO, bukan stack.

cpp
#include <iostream>
#include <queue>

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 levelorder(const Node<T>* root) {
    if (root == nullptr) return;
    std::queue<const Node<T>*> q;
    q.push(root);
    while (!q.empty()) {
        const Node<T>* n = q.front(); q.pop();
        std::cout << n->data << ' ';
        if (n->left)  q.push(n->left);
        if (n->right) q.push(n->right);
    }
}

int main() {
    Node<char>* f = new Node<char>('F');
    Node<char>* b = new Node<char>('B');
    Node<char>* g = new Node<char>('G');
    Node<char>* a = new Node<char>('A');
    Node<char>* d = new Node<char>('D');
    Node<char>* i = new Node<char>('I');
    Node<char>* c = new Node<char>('C');
    Node<char>* e = new Node<char>('E');
    Node<char>* h = new Node<char>('H');

    f->left = b;  f->right = g;
    b->left = a;  b->right = d;
    d->left = c;  d->right = e;
    g->right = i;
    i->left = h;

    std::cout << "Level-order : ";
    levelorder(f);
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Level-order : F B G A D I C E H

std::queue<const Node<T>*>: queue FIFO menjamin node yang didorong lebih dulu akan diproses lebih dulu.
Push root, lalu loop: pop depan, cetak, dorong left lalu right. Pola ini secara alami menghasilkan urutan per-level: root (level 0), lalu kedua anak (level 1), lalu cucu (level 2), dan seterusnya.
Urutan F B G A D I C E H: level 0 = F. Level 1 = B, G. Level 2 = A, D, I. Level 3 = C, E, H. Sesuai diagram tree di atas.

Kompleksitas dan Pemilihan Strategi #

Strategi	Waktu	Ruang	Cocok untuk
Pre-order	O(n)	O(h) stack	Serialize tree, copy tree
In-order	O(n)	O(h) stack	BST → urutan terurut, validasi BST
Post-order	O(n)	O(h) stack	Hapus tree, evaluasi expression
Level-order	O(n)	O(w) queue, w = lebar maksimum	Pencarian level, BFS shortest path

h adalah height tree; w adalah lebar maksimum. Pada skewed tree, h = O(n); pada balanced tree, h = O(log n).

Ringkasan #

Pre-order (Node-Left-Right): root pertama; cocok untuk serialize/copy tree.
In-order (Left-Node-Right): root di tengah; pada BST menghasilkan urutan terurut.
Post-order (Left-Right-Node): root terakhir; cocok untuk hapus tree dan evaluasi expression tree.
Level-order (BFS): kunjungi per level dengan queue; cocok untuk BFS dan shortest path pada tree tak berbobot.
Implementasi rekursif memakai call stack; iteratif memakai std::stack eksplisit. Level-order memakai std::queue.
Semua traversal memiliki kompleksitas waktu O(n) dan ruang O(h) (atau O(w) untuk level-order).