Trees, Traversals, and Spanning Trees: Definitions, Algorithms, and Applications

TAKEAWAYS:

• Trees are non-linear, hierarchical data structures with no cycles, used to model relationships like file systems, organizational charts, or game AI decision trees.
• Traversals (pre-order, in-order, post-order) visit every node systematically: pre-order (root → left → right) is used in copying trees, post-order (left → right → root) in deleting nodes.
• A spanning tree connects all vertices of a graph with the fewest edges (no cycles), and a minimum spanning tree (MST) minimizes total edge weight—critical for network design (e.g., NTC’s fiber-optic backbone).
• Kruskal’s algorithm builds an MST by sorting edges by weight and adding them if they don’t create cycles (uses Union-Find for efficiency).
• Trees enable efficient searching (O(log n) in balanced trees) and recursive algorithms (e.g., directory traversal in Linux’s find command).
• Real-world ties: Pathao’s ride-matching uses trees to optimize driver-customer pairing; NEPSE’s stock hierarchy is a tree of companies/sector indices.

---

1. Trees: Definition and Properties

A tree is a connected acyclic graph with:

• Nodes (vertices): Elements (e.g., files, users).
• Edges: Parent-child relationships.
• Root: The topmost node (no parent).
• Leaf: A node with no children.

Key Properties

• n nodes → n−1 edges.
• Path: Unique sequence of edges between any two nodes.
• Subtree: A tree derived from a node and its descendants.

Example: File system hierarchy (root /, directories as nodes, files as leaves).

---

2. Tree Traversals

Traversals visit nodes in a specific order. Three primary methods:

A. Pre-order Traversal (Root → Left → Right)

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

Algorithm:

def preorder(node):
    if node:
        print(node.data)       # 1. Visit root
        preorder(node.left)    # 2. Left subtree
        preorder(node.right)   # 3. Right subtree

Example: Copying a tree or printing directory structures (e.g., ls -R in Linux). Trace:

        A
       / \
      B   C
     / \   \
    D   E   F

Output: A → B → D → E → C → F

---

B. In-order Traversal (Left → Root → Right)

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

Use Case: Binary search trees (BSTs) yield nodes in sorted order. Trace (same tree): Output: D → B → E → A → F → C

---

C. Post-order Traversal (Left → Right → Root)

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

Use Case: Deleting a tree (children before parent) or evaluating expressions (e.g., 3 + 4 * 2 → post-order: 3 4 2 * +). Trace (same tree): Output: D → E → B → F → C → A

---

Comparison Table

---

3. Spanning Trees and Minimum Spanning Trees (MST)

A. Spanning Tree

A subgraph that:

• Connects all vertices.
• Has no cycles.
• Uses n−1 edges (for n vertices).

Example: NTC’s fiber-optic network connecting 5 cities (vertices) with 4 cables (edges) without loops.

Spanning Tree: Remove edge B-D (cycle A-B-D-C-A), leaving edges A-B, A-C, C-D, D-E.

---

B. Minimum Spanning Tree (MST)

A spanning tree with the minimum total edge weight. Applications:

• Ncell’s mobile network: Minimizes signal tower costs.
• Daraz’s delivery routes: Shortest paths between warehouses.
• Khalti’s payment network: Lowest transaction fees between banks.

Kruskal’s Algorithm (Greedy Approach)

1. Sort all edges by weight (ascending).
2. Add edges to the MST if they don’t form a cycle (use Union-Find).
3. Stop when n−1 edges are added.

Steps for the above graph:

1. Sort edges: D-E (2), C-D (3), A-C (5), B-D (1), A-B (10).
2. Add D-E (no cycle).
3. Add C-D (no cycle).
4. Add A-C (no cycle).
5. Skip B-D (creates cycle A-B-D-C-A).
6. MST: Edges D-E, C-D, A-C (total weight = 10).

Union-Find Pseudocode:

def find(u):
    while parent[u] != u:
        u = parent[u]
    return u

def union(u, v):
    rootU = find(u)
    rootV = find(v)
    if rootU != rootV:
        parent[rootV] = rootU

---

4. Real-World Applications

A. Pathao’s Ride-Matching System

• Tree Structure: Cities are nodes; roads are edges.
• MST: Optimizes driver-customer pairing by minimizing travel time (shortest paths = MST edges).
• Traversals: Pre-order to assign nearest available driver.

B. NEPSE’s Stock Hierarchy

• Tree: Companies are nodes; sectors (e.g., banking, IT) are parent nodes.
• Traversals: In-order to list stocks alphabetically by sector.

C. Bank Loan Interest Calculation (Recursive Trees)

• Problem: A loan of ₹10,000 at 5% annual interest for 3 years. How much is owed?
• Tree Model:
  • Year 0: ₹10,000
  • Year 1: ₹10,000 + 5% = ₹10,500
  • Year 2: ₹10,500 + 5% = ₹11,025
  • Year 3: ₹11,025 + 5% = ₹11,576.25
• Recursive Formula: A = P * (1 + r)^n (where P = principal, r = rate, n = years).

---

5. Exam Tip

• Definitions: Know the exact wording for spanning tree, MST, and traversal types. For example:

  "A spanning tree of a connected graph G is a subgraph that includes all vertices of G and is a tree."

• Kruskal’s Algorithm: Always sort edges first and use Union-Find to avoid cycles. Show step-by-step edge addition in exams.
• Traversal Examples: Draw the tree and write the output sequence for pre/in/post-order. Use the same tree for all three to save time.
• Real-World Links: Relate MSTs to NTC’s network or Pathao’s routes; traversals to file systems or expression trees.
• Common Pitfalls:
  • Forgetting to sort edges in Kruskal’s.
  • Missing the base case in recursive traversals (e.g., if node is None).
  • Adding a cycle in the MST (always check with Union-Find).

---

Practice Question: Given the graph below, use Kruskal’s algorithm to find the MST and calculate its total weight.

Vertices: A, B, C, D
Edges: A-B (4), A-C (2), B-C (1), B-D (5), C-D (8)

Solution:

1. Sort edges: B-C (1), A-C (2), A-B (4), B-D (5), C-D (8).
2. Add B-C (no cycle).
3. Add A-C (no cycle).
4. Skip A-B (cycle A-B-C-A).
5. Add B-D (no cycle). MST Edges: B-C, A-C, B-D → Total Weight = 1 + 2 + 5 = 8.