Introduction to Trees and Graphs

# CHAPTER 1

Introduction to Trees and Graphs #

1. Introduction #

2. Learning Objectives #

• Define what Trees and Graphs are in computer science.

• Differentiate between linear and non-linear data structures.

• Understand the real-world applications of Trees and Graphs.

• Conceptualize hierarchical vs. network structures.

3. What are Trees? #

• It starts with a single top-level node called the Root.

• It branches down to child nodes.

• A tree strictly prohibits cycles (loops). You cannot traverse from a child back to its parent using a downward path.

Visual Example:

        CEO (Root)
       /   \
   VP(A)   VP(B)
   /  \      \
Mgr1 Mgr2   Mgr3

4. What are Graphs? #

• A Tree is actually just a special, restricted type of Graph!

Visual Example:

A --- B
|     |
C --- D

*(In this graph, A is connected to B and C. You can travel from A to B, B to D, D to C, and C back to A, creating a cycle).*

5. Hierarchical vs. Network Structures #

• Hierarchical (Trees): Represents a "One-to-Many" relationship. Data flows from top to bottom.

• *Analogy:* A family tree. You have parents, who have children.

• Network (Graphs): Represents a "Many-to-Many" relationship. Data flows in any direction.

• *Analogy:* A city's subway system. Multiple stations (Vertices) connect to multiple other stations via train tracks (Edges).

6. Why Trees and Graphs Matter #

7. Real-World Applications #

• File Systems: Your computer's folder structure (Root: C:\ -> Users -> Documents).

• Databases: B-Trees are used to index database records for ultra-fast retrieval.

• Compilers: Abstract Syntax Trees (AST) parse the code you write.

• HTML DOM: The Document Object Model of every webpage is a Tree.

Applications of Graphs:

• Social Networks: Facebook and LinkedIn use graphs (Users are Nodes, Friendships are Edges).

• Mapping/GPS: Google Maps uses graphs to find the shortest route between cities.

• Network Routing: The internet uses graphs to route packets from your router to a server.

8. Mini Project: Organizational Chart #

C++:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Node {
    string name;
    string title;
    vector<Node*> reports;
    
    Node(string n, string t) {
        name = n;
        title = t;
    }
};

int main() {
    Node* ceo = new Node("Alice", "CEO");
    Node* vp1 = new Node("Bob", "VP Engineering");
    Node* vp2 = new Node("Charlie", "VP Sales");
    
    ceo->reports.push_back(vp1);
    ceo->reports.push_back(vp2);
    
    cout << ceo->title << " has " << ceo->reports.size() << " direct reports." << endl;
    return 0;
}

Java:

import java.util.ArrayList;
import java.util.List;

class Node {
    String name;
    String title;
    List<Node> reports;

    public Node(String name, String title) {
        this.name = name;
        this.title = title;
        this.reports = new ArrayList<>();
    }
}

public class Main {
    public static void main(String[] args) {
        Node ceo = new Node("Alice", "CEO");
        Node vp1 = new Node("Bob", "VP Engineering");
        
        ceo.reports.add(vp1);
        System.out.println(ceo.title + " has " + ceo.reports.size() + " direct report.");
    }
}

Python:

class Node:
    def __init__(self, name, title):
        self.name = name
        self.title = title
        self.reports = []

ceo = Node("Alice", "CEO")
vp1 = Node("Bob", "VP Engineering")
ceo.reports.append(vp1)

print(f"{ceo.title} has {len(ceo.reports)} direct report(s).")

9. Complexity Analysis #

• Time Complexity (Creation): $O(1)$ to create a single node.

• Space Complexity: $O(N)$ where $N$ is the number of nodes in the structure, as each node requires memory allocation.

10. Common Mistakes #

• Confusing Trees with Graphs: Remember, all Trees are Graphs, but not all Graphs are Trees. If a structure has a cycle (a loop), it is mathematically a Graph, NOT a Tree.

11. Best Practices #

• When dealing with hierarchical data, always default to a Tree structure rather than trying to force it into a 2D Array or Linked List.

12. Exercises #

1. 1. Draw a visual tree representing the folder structure of your computer's Desktop.

1. 2. Draw a visual graph representing your 5 closest friends and who is friends with whom.

13. MCQs with Answers #

14. Interview Questions #

• Q: Explain the fundamental difference between a Tree and a Graph.

• Q: If you were designing a recommendation engine like Netflix, would you use a Tree or a Graph, and why?

15. Summary #

16. Next Chapter Recommendation #