Skip to main content

Tree Concept

Module 6: Tree

Author: YP

Learning1. ObjectivesTheoretical Background

1.1 Binary Tree

After completing this module, students are expected to be able to:

  1. Explain the basic concepts ofA 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).
    • Implement basicBasic operations on BST: (insert, search, deletedelete) 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. UnderstandInsert – 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 performadjust variousthe 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. traversalTraversal methods:– visit all nodes using Inorder, Preorder, Postorder, andor Level Order.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.
    • RecognizeTypically 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 useroot 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 asin implementationsC++ ofuse 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 (Red-Black:

    Tree).
            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]
    Back to top