Skip to main content

Tree Concept

1. Theoretical Background

1.1 Binary Tree

A Binary Tree is a tree data structure where each node has at most two children (left and right).

  • No special rules apply to the placement of node values.
  • Used for representing hierarchies, data structures such as heaps, expression trees, and the implementation of search or traversal algorithms.
  • A node in a Binary Tree can have 0, 1, or 2 children.

Characteristics of a Binary Tree:

  • Tree height: the number of levels from the root to the farthest leaf.
  • Leaf node: a node that has no children.

Example of a Binary Tree Structure:

image

image

1.2 Binary Search Tree (BST)

A Binary Search Tree (BST) is a type of Binary Tree with special rules:

  • All nodes in the left subtree have values smaller than the root node.
  • All nodes in the right subtree have values greater than the root node.

Advantages of BST:

  • Enables faster data searching compared to a regular Binary Tree, since half of the tree can be ignored at each search step (similar to the binary search algorithm).
  • Basic operations (insert, search, delete) can be performed with an average time complexity of O(log n).

Example of a BST Structure:

image

1.3 Basic Operations on BST

  1. Insert – add a new node at the correct position according to BST rules.
Node* insert(Node* root, int value) {
    // Base Case: Jika tree atau subtree kosong, buat node baru di sini
    if (root == nullptr) {
        return createNode(value);
    }

    // Langkah Rekursif:
    if (value < root->data) {
        // Panggil insert untuk subtree kiri
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        // Panggil insert untuk subtree kanan
        root->right = insert(root->right, value);
    }

    // Kembalikan root yang (mungkin) tidak berubah
    return root;
}
  1. Search – find a node with a specific value using the BST property.
bool search(Node* root, int value) {
    // Base Case 1: tree kosong, nilai tidak ditemukan
    if (root == nullptr) {
        return false;
    }

    // Base Case 2: Nilai ditemukan di root saat ini
    if (root->data == value) {
        return true;
    }

    // Langkah Rekursif:
    if (value < root->data) {
        return search(root->left, value);
    } else {
        return search(root->right, value);
    }
}
  1. Delete – remove a node and adjust the structure so that the BST rules remain valid.
// Fungsi mencari node dengan nilai minimum (untuk delete)
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr)
        current = current->left;
    return current;
}

// Fungsi delete pada BST
Node* deleteNode(Node* root, int value) {
    if (root == nullptr) return root;

    if (value < root->data)
        root->left = deleteNode(root->left, value);
    else if (value > root->data)
        root->right = deleteNode(root->right, value);
    else {
        // Kasus 1: Node tidak punya anak
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // Kasus 2: Node hanya punya satu anak
        else if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        // Kasus 3: Node punya dua anak
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}
  1. Traversal – visit all nodes using Inorder, Preorder, Postorder, or Level Order methods.

1.4 Tree Traversal

Traversal is the process of visiting each node in the tree.

1. Inorder (Left, Root, Right)

  • Visit the left subtree first, then the root, then the right subtree.
  • Typically produces data in ascending order.
// Inorder (Kiri - Root - Kanan)
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

2. Preorder (Root, Left, Right)

  • Visit the root first, then the left subtree, then the right subtree.
  • Useful for representing the structure of a tree.
// Preorder (Root - Kiri - Kanan)
void preorder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

3. Postorder (Left, Right, Root)

  • Visit the left subtree first, then the right subtree, and finally the root.
  • Suitable for deleting or freeing all nodes in the tree.
// Postorder (Kiri - Kanan - Root)
void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

4. Level Order

  • Visit nodes level by level from top to bottom, left to right.
  • Commonly implemented using a queue.
void levelOrder(Node* root) {
    if (root == nullptr) return;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        cout << current->data << " ";
        q.pop();

        if (current->left != nullptr) q.push(current->left);
        if (current->right != nullptr) q.push(current->right);
    }
}

1.5 STL and Balanced BST

  • std::map and std::set in C++ use a Red-Black Tree, which is a balanced BST.
  • Advantages: insertion, search, and deletion operations are consistently O(log n) without requiring manual balancing.

Example Code std::set

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> angka;

    // Menambahkan elemen
    angka.insert(5);
    angka.insert(2);
    angka.insert(8);
    angka.insert(2); // duplikat, tidak akan ditambahkan

    cout << "Isi set (otomatis terurut & unik): ";
    for (int x : angka) {
        cout << x << " ";
    }
    cout << endl;

    // Mengecek apakah elemen ada
    if (angka.find(5) != angka.end()) {
        cout << "Angka 5 ditemukan dalam set." << endl;
    }

    return 0;
}

Example Code std::map

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> siswa;

    // Menambahkan pasangan key-value
    siswa[101] = "Andi";
    siswa[102] = "Budi";
    siswa[103] = "Cici";

    // Menampilkan isi map
    cout << "Daftar siswa:" << endl;
    for (auto& [id, nama] : siswa) {
        cout << id << " : " << nama << endl;
    }

    // Mengecek apakah key ada
    if (siswa.find(102) != siswa.end()) {
        cout << "Siswa dengan ID 102 adalah " << siswa[102] << endl;
    }

    return 0;
}

2. Traversal Illustration Example

BST :

        50
       /  \
      /    \
     30    70
    / \   / \
   20 40 60  80
  • Inorder: 20, 30, 40, 50, 60, 70, 80
  • Preorder: 50, 30, 20, 40, 70, 60, 80
  • Postorder: 20, 40, 30, 60, 80, 70, 50
  • Level Order: 50, 30, 70, 20, 40, 60, 80

References

  • GeeksforGeeks, “Binary Search Tree (BST),” [Online]. Available: https://www.geeksforgeeks.org/binary-search-tree-data-structure/. [Accessed: 20-August-2025]
  • Programiz, “Tree Data Structure in C++,” [Online]. Available: https://www.programiz.com/dsa/binary-search-tree. [Accessed: 20-August-2025]

No comments to display

Back to top