2. Tree Concept

2.1 TheoreticalBasic BackgroundTheory

2.1.1 Definition of a Tree

A Tree is a non-linear hierarchical data structure composed of nodes and edges.

• Every Tree has a root (root node).
• The root can have children.
• A node with no children is called a leaf.
• Each node and its descendants can form a subtree.

2.1.2 Important Terms in a Tree

• Root → the topmost node.
• Parent → a node that has children.
• Child → a node derived from a parent.
• Leaf → a node without children.
• Subtree → a small tree formed from a node and its descendants.

2.1.3 Binary Tree

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

• NoThere are no special rules applyfor to the placement ofplacing node values.
• Used for representinghierarchical hierarchies,representation, data structures such aslike heaps, expression trees, and the implementation ofimplementing search or traversal algorithms.
• A nodeNodes in a Binary Tree can have 0, 1, or 2 children.

Characteristics of a Binary Tree:

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

---

2.2 Introduction to Stack and Queue

Example2.2.1 of a Binary Tree Structure:Stack

---

2.1.2 Binary Search Tree (BST)

A Binary Search TreeLIFO (BST)Last In First Out) data structure → the last data in is the first one out. Example: a typestack of Binaryplates Treein witha specialcafeteria. rules:The last plate placed on top will be the first one taken.

Main operations:

• Allpush(x) nodes→ inadds data to the lefttop subtree have values smaller thanof the root node.stack.
• Allpop() nodes→ inremoves data from the righttop subtree have values greater thanof the root node.stack.

AdvantagesApplication ofin BST:Trees Used in DFS (Depth First Search) or Preorder, Inorder, Postorder traversals. When we enter a child node, the current node is stored on the stack. After finishing with the child, we pop from the stack to continue.

2.2.2 Queue

A FIFO (First In First Out) data structure → the first data in is the first one out. Example: a minimarket cashier line, the person who arrives first will be served first.

Main operations:

• Enablesenqueue(x) faster→ inserts data searchingat comparedthe to a regular Binary Tree, since halfback of the treequeue.
can
• dequeue() be→ ignoredremoves atdata each search step (similar tofrom the binary search algorithm).
• Basic operations (insert, search, delete) can be performed with an average time complexityfront of O(logthe n).queue.

ExampleApplication ofin a BST Structure:

2.1.3 Basic Operations on BST

a. InsertTrees –Used addin 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
    ifBFS (rootBreadth ==First 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;
}

b. 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);
    }
}

c. 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;
}

4. Traversal – visit all nodes using Inorder, Preorder, Postorder,Search) or Level Order methods.
traversal.

When visiting a node, its children are added to the queue, then processed one by one in order.

---

2.1.4 Tree3 Traversal

 in Trees

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

a.2.3.1 Inorder (Left, Root, Right)

• Visitvisit the left subtree first,left, then the root,middle (root), then the rightright. subtree.
The
• Typicallyresult producesis usually data sorted in ascending order.

// Inorder (KiriLeft - Root - Kanan)Right)
void inorder(Node* root) {
   if (root == nullptr) return;
   inorder(root->left);
   cout << root->data << " ";
   inorder(root->right);
}

b.2.3.2 Preorder (Root, Left, Right)

• Visitvisit the rootmiddle first, then the left subtree,left, then the rightright. subtree.
Used
• Usefulto for representingrepresent the structure of athe tree.

// Preorder (Root - KiriLeft - Kanan)Right)
void preorder(Node* root) {
   if (root == nullptr) return;
   cout << root->data << " ";
   preorder(root->left);
   preorder(root->right);
}

c.2.3.3 Postorder (Left, Right, Root)

• Visitvisit the left subtree first, then the right subtree, andright, finally the root.
middle.
• Suitable forif deletingyou orwant freeingto delete all nodescontents inof the tree.

// Postorder (KiriLeft - KananRight - Root)
void postorder(Node* root) {
   if (root == nullptr) return;
   postorder(root->left);
   postorder(root->right);
   cout << root->data << " ";
}

d.2.3.4 Level Order

• Visit nodes level by level from top to bottom, left to right.
• CommonlyUsually implemented usinguses a queue.

void levelOrder(Node* root) {
   if (root == nullptr) return;
   queue<Node*> q;
   q.push(root);
   while (!q.empty()) {
   Node* currenttemp = q.front();
   q.pop();
   cout << current-temp->data << " ";
   q.pop();

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

---

2.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.23.5 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]