Tree Concept

1. Theoretical BackgroundTheory

1.1 BinaryDefinition Treeof Graph

A Binary TreeGraph is a tree data structure whereconsisting each node has at most two children (left and right).of:

• NoVertex special rules(node) apply→ torepresents thean placement of node values.object.
• UsedEdge for→ representing hierarchies, data structures such as heaps, expression trees, andrepresents the implementationrelationship ofbetween search or traversal algorithms.
• A node in a Binary Tree can have 0, 1, or 2 children.objects.

CharacteristicsGraphs ofcan a Binary Tree:be:

• TreeDirected height:or Undirected.
• Weighted or Unweighted.

---

1.2 Graph Representation

There are two main representations of graphs in programming:

1. Adjacency Matrix
   A 2D matrix [V][V], where V is the number of levelsvertices. fromEach theelement rootindicates towhether thean farthestedge leaf.

exists
2. Leafbetween node:two anodes node(commonly that1 hasfor an edge, 0 for no children.

Example of a Binary Tree Structure:





---

1.2 Binary Search Tree (BST)

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

• AllSuitable nodesfor dense graphs.
• Edge lookup is efficient with O(1) time complexity.

int graph[5][5] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

3. Adjacency List
   Each vertex stores a list of its adjacent vertices (neighbors).

   • Memory-efficient for sparse graphs, as only existing edges are stored.
   • Edge lookup may take up to O(V) in the leftworst subtree have values smaller than the root node.
   • All nodes in the right subtree have values greater than the root node.case.

   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:

   

   1.3 Basic Operations on BST

   1. Insert – add a new node at the correct position according to BST rules.

   Node*vector<int> insert(Node* root, int value) {
       // Base Case: Jika tree atau subtree kosong, buat node baru di sini
       if (root == nullptr) {
           return createNode(value)adj[5];
   
   }
   
       // Langkah Rekursif:
       if (value < root->data) {
           // Panggil insert untuk subtree kiri
           root->left = insert(root->left, value)adj[0].push_back(1);
   } else if (value > root->data) {
           // Panggil insert untuk subtree kanan
           root->right = insert(root->right, value)adj[0].push_back(4);
   }adj[1].push_back(0);
   //adj[1].push_back(2);
   Kembalikan root yang (mungkin) tidak berubah
       return root;
   }adj[1].push_back(3);
   

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

   3. 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, or Level Order methods.

   ---

   1.43 TreeGraph Traversal

   TraversalGraph istraversal thecan processbe of visiting each nodeperformed in thetwo tree.main ways:

   1. 1.Breadth InorderFirst Search (Left, Root, Right)BFS)

      • VisitUses thea left subtree first, then the root, then the right subtree.queue.
      • 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

      • VisitExplores nodes level by level from(broad topexploration).
      • Effective in unweighted graphs to bottom,find leftthe shortest path from one node to right.
      • Commonly implemented using a queue.another.

      void levelOrder(Node*BFS(int root)start, vector<int> adj[], int V) {
          ifvector<bool> (rootvisited(V, == nullptr) return;false);
          queue<Node*int> q;
      
          visited[start] = true;
          q.push(root)start);
      
          while (!q.empty()) {
              Node*int currentu = q.front();
              q.pop();
              cout << current->datau << " ";
      
              for (int v : adj[u]) {
                  if (!visited[v]) {
                      visited[v] = true;
                      q.push(v);
                  }
              }
          }
      }
      

   2. Depth First Search (DFS)

      • Uses recursion or a stack.
      • Explores as deep as possible before backtracking.
      • Useful for detecting cycles, performing topological sort, or finding connected components.

      void DFSUtil(int u, vector<int> adj[], vector<bool>& visited) {
          visited[u] = true;
          cout << u << " ";
          for (int v : adj[u]) {
              if (!visited[v]) {
                  DFSUtil(v, adj, visited);
              }
          }
      }
      
      void DFS(int start, vector<int> adj[], int V) {
          vector<bool> visited(V, false);
          DFSUtil(start, adj, visited);
      }
      

   ---

   1.4 Shortest Path Algorithm: Dijkstra

   • Finds the shortest path from a source node to all other nodes in a positively weighted graph.
   • Uses a priority queue (min-heap) to efficiently select edges with the smallest weights.
   • Time complexity: O((V + E) log V).

   void dijkstra(int V, vector<pair<int,int>> adj[], int src) {
       vector<int> dist(V, INT_MAX);
       dist[src] = 0;
   
       priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
       pq.push({0, src});
   
       while (!pq.empty()) {
           int u = pq.top().second;
           pq.pop();
   
           iffor (current->leftauto !=[v, nullptr)w] q.push(current->left);: adj[u]) {
               if (current->rightdist[u] !+ w < dist[v]) {
                   dist[v] = nullptr)dist[u] q.+ w;
                   pq.push(current->right){dist[v], v});
               }
           }
       }
   
       cout << "Jarak terpendek dari " << src << ":\n";
       for (int i = 0; i < V; i++) {
           cout << "Ke " << i << " = " << dist[i] << endl;
       }
   }
   

   ---

   1.5 STLMinimum andSpanning BalancedTree BST(MST)

   Prim’s Algorithm

   • std::mapStarts and std::set in C++ usefrom a Red-Blacksingle Tree,node, whichrepeatedly isadding the minimum weight edge that connects a balancednew BST.node to the tree.
   • Advantages:Efficient insertion, search, and deletion operations are consistentlywith O(E log n)V) withoutcomplexity requiringusing manuala balancing.priority queue.
   • Suitable for dense graphs.

   Example Code std::set

   #include <iostream>
   #include <setbits/stdc++.h>
   using namespace std;
   
   const int main()INF = 1e9;
   
   void primMST(int n, vector<vector<pair<int, int>>> &adj) {
       setvector<int> angka;key(n, // Menambahkan elemen
       angka.insert(5)INF);
       angka.insert(2)vector<bool> inMST(n, false);
       angka.insert(8);vector<int> angka.insert(2)parent(n, -1);
   
       // duplikat,Mulai tidakdari akannode ditambahkan0
       coutkey[0] = 0;
       priority_queue<pair<int, "Isiint>, setvector<pair<int, int>>, greater<>> pq;
       pq.push({0, 0}); // {weight, node}
   
       while (otomatis!pq.empty()) terurut{
           &int unik):u "= pq.top().second;
           pq.pop();
   
           if (inMST[u]) continue;
           inMST[u] = true;
   
           for (intauto x&[v, w] : angka)adj[u]) {
               coutif (!inMST[v] && w << xkey[v]) <<{
                   "key[v] "= w;
                   pq.push({key[v], v});
                   parent[v] = u;
               }
           }
       }
   
       cout << endl;"Edges //in Mengecek apakah elemen ada
       ifMST (angka.find(5)Prim):\n";
       !for (int i = angka.end()1; i < n; i++) {
           cout << parent[i] << "Angka 5- ditemukan dalam set." << endl;i << "\n";
       }
   return}
   
   0;int main() {
       int n = 5;
       vector<vector<pair<int, int>>> adj(n);
   
       // contoh graf berbobot (undirected)
       adj[0].push_back({1, 2});
       adj[1].push_back({0, 2});
   
       adj[0].push_back({3, 6});
       adj[3].push_back({0, 6});
   
       adj[1].push_back({2, 3});
       adj[2].push_back({1, 3});
   
       adj[1].push_back({3, 8});
       adj[3].push_back({1, 8});
   
       adj[1].push_back({4, 5});
       adj[4].push_back({1, 5});
   
       adj[2].push_back({4, 7});
       adj[4].push_back({2, 7});
   
       primMST(n, adj);
   }
   
   

   ExampleKruskal’s CodeAlgorithm

   std::map
   • Sorts all edges by weight, then adds them one by one as long as they do not form a cycle.
   • Uses Disjoint Set Union (DSU) to detect and prevent cycles.
   • Time complexity: O(E log E).
   • More efficient for sparse graphs.

   #include <iostream>
   #include <mapbits/stdc++.h>
   using namespace std;
   
   intstruct main()Edge {
       mapint u, v, w;
       bool operator<int,(const stringEdge &other) const {
           return w < other.w;
       }
   };
   
   struct DSU {
       vector<int> siswa;parent, //rank;
       MenambahkanDSU(int pasangann) key-value{
           siswa[101]parent.resize(n);
           rank.resize(n, 0);
           iota(parent.begin(), parent.end(), 0);
       }
   
       int find(int x) {
           if (x != parent[x])
               parent[x] = "Andi"find(parent[x]);
           siswa[102]return parent[x];
       }
   
       bool unite(int a, int b) {
           a = "Budi"find(a);
           siswa[103]b = "Cici"find(b);
           //if Menampilkan(a isi== mapb) return false;
           if (rank[a] < rank[b]) swap(a, b);
           parent[b] = a;
           if (rank[a] == rank[b]) rank[a]++;
           return true;
       }
   };
   
   void kruskalMST(int n, vector<Edge> &edges) {
       sort(edges.begin(), edges.end());
       DSU dsu(n);
   
       cout << "DaftarEdges siswa:"in <<MST endl;(Kruskal):\n";
       for (auto & [id, nama]e : siswa)edges) {
           cout << id << " : " << nama << endl;
       }
   
       // Mengecek apakah key ada
           if (siswa.find(102)dsu.unite(e.u, != siswa.end()e.v)) {
               cout << e.u << "Siswa dengan ID 102 adalah- " << siswa[102]e.v << endl;"\n";
           }
       return}
   0;}
   
   int main() {
       int n = 5;
       vector<Edge> edges = {
           {0, 1, 2}, {0, 3, 6}, {1, 2, 3},
           {1, 3, 8}, {1, 4, 5}, {2, 4, 7}
       };
   
       kruskalMST(n, edges);
   }
   
   

   ---

   2. Example of Graph Traversal Illustration Example

   BSTExample :of an undirected weighted graph:

           50
          /  \
         /    \
        30    70
       / \   / \
      20 40 60  80
   

   

   • Inorder:BFS (starting from node 0)
     20,Traversal 30,per 40,level 50,(broad):
     60,0 70,→ 801 → 2 → 3

   • Preorder:DFS (starting from node 0)
     50,Traversal 30,as 20,deep 40,as 70,possible 60,before 80backtracking:
     0 → 1 → 3 → 2
     (order may vary depending on implementation, e.g., 0 → 1 → 2 → 3)

   • Postorder:Dijkstra (shortest path from node 0)

     • Distance to 0 20,= 40, 30, 60, 80, 70, 500
     • Distance to Level Order:1 50,= 30,4
     70,
     • Distance 20,to 40,2 60,= 801
     • Distance to 3 = 6

     ---

     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]