Why Graphs Exist and What Trees Cannot Model in DSA C - Why This Pattern

Mental Model

Graphs let us connect things in many ways, not just in a strict family tree style. Trees are like family trees with one clear parent, but graphs can show friendships or roads where many connections happen.

Analogy: Imagine a group of friends where everyone can be friends with many others, not just one parent or child like in a family tree. This is like a graph, while a family tree is like a tree structure.

Tree:
  A
 / \
B   C

Graph:
A --- B
| \   |
C --- D

Dry Run Walkthrough

Input: A family tree with nodes A, B, C where A is parent of B and C; and a friendship network where A, B, C, D are friends connected in many ways.

Goal: Show why trees cannot represent multiple connections like friendships, but graphs can.

Step 1: Draw a tree with A as root and B, C as children

A -> B
|
-> C

Why: Trees show one parent with children, no cycles or multiple parents

Step 2: Try to add a friendship between B and C in the tree

A -> B
|    ↘
-> C -- (cannot add edge in tree)

Why: Trees cannot have edges between siblings or cycles

Step 3: Draw a graph with A, B, C, D connected in many ways

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

Why: Graphs allow multiple connections, cycles, and no strict parent-child

Result:

Graph:
A --- B
| \   |
C --- D
Trees cannot model these multiple connections or cycles.

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Simple tree node
typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Simple graph node with adjacency list
typedef struct GraphNode {
    char val;
    struct GraphNode** neighbors;
    int neighborCount;
} GraphNode;

// Create tree node
TreeNode* createTreeNode(char val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Create graph node
GraphNode* createGraphNode(char val) {
    GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
    node->val = val;
    node->neighbors = NULL;
    node->neighborCount = 0;
    return node;
}

// Add neighbor to graph node
void addNeighbor(GraphNode* node, GraphNode* neighbor) {
    node->neighborCount++;
    node->neighbors = (GraphNode**)realloc(node->neighbors, node->neighborCount * sizeof(GraphNode*));
    node->neighbors[node->neighborCount - 1] = neighbor;
}

// Print tree (preorder)
void printTree(TreeNode* root) {
    if (!root) return;
    printf("%c ", root->val);
    printTree(root->left);
    printTree(root->right);
}

// Print graph adjacency
void printGraph(GraphNode** nodes, int count) {
    for (int i = 0; i < count; i++) {
        printf("%c: ", nodes[i]->val);
        for (int j = 0; j < nodes[i]->neighborCount; j++) {
            printf("%c ", nodes[i]->neighbors[j]->val);
        }
        printf("\n");
    }
}

int main() {
    // Build tree: A -> B, C
    TreeNode* A = createTreeNode('A');
    TreeNode* B = createTreeNode('B');
    TreeNode* C = createTreeNode('C');
    A->left = B;
    A->right = C;

    printf("Tree (preorder): ");
    printTree(A);
    printf("\n");

    // Build graph: A-B, A-C, B-D, C-D
    GraphNode* GA = createGraphNode('A');
    GraphNode* GB = createGraphNode('B');
    GraphNode* GC = createGraphNode('C');
    GraphNode* GD = createGraphNode('D');

    addNeighbor(GA, GB);
    addNeighbor(GA, GC);
    addNeighbor(GB, GD);
    addNeighbor(GC, GD);

    GraphNode* graphNodes[] = {GA, GB, GC, GD};

    printf("Graph adjacency:\n");
    printGraph(graphNodes, 4);

    return 0;
}

A->left = B; A->right = C;

Set left and right children to build tree structure

addNeighbor(GA, GB); addNeighbor(GA, GC); addNeighbor(GB, GD); addNeighbor(GC, GD);

Add edges to graph nodes to build multiple connections

Output

Tree (preorder): A B C 

Graph adjacency:

A: B C 

B: D 

C: D 

D: 

Complexity Analysis

Time: O(n) because printing visits each node once

Space: O(n) for storing nodes and their connections

vs Alternative: Trees have simpler structure with one parent per node, graphs allow multiple edges increasing complexity but modeling power

Edge Cases

Empty tree or graph

Print functions handle null pointers gracefully without crashing

DSA C

if (!root) return;

Graph node with no neighbors

Prints node with empty adjacency list

DSA C

for (int j = 0; j < nodes[i]->neighborCount; j++)

When to Use This Pattern

When a problem involves multiple connections between items without a strict hierarchy, think of graphs instead of trees because graphs model complex relationships like cycles and many-to-many links.

Common Mistakes

Mistake: Trying to represent multiple connections or cycles using a tree structure
Fix: Use a graph data structure that allows multiple edges and cycles

Summary

Graphs model complex connections including cycles and many-to-many relationships.

Use graphs when relationships are not strictly hierarchical or tree-like.

The key insight is that trees are a special kind of graph with strict parent-child rules, but graphs can represent any connection pattern.