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

Mental Model

Graphs let us connect things in many ways, not just in a strict family tree style. Trees only show one path between points, but graphs can show many paths and loops.

Analogy: Imagine a city map: streets connect places in many ways, sometimes looping back or crossing. A tree is like a family tree, showing only one path from ancestor to child, no loops or shortcuts.

Tree:
  A
 / \
B   C

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

Dry Run Walkthrough

Input: Tree with nodes A, B, C; Graph with nodes A, B, C, D and edges A-B, B-D, D-C, C-A

Goal: Show that trees cannot represent loops or multiple connections between nodes, but graphs can

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

A -> B
  ↓
  C
No loops or multiple paths

Why: Trees have a strict parent-child structure with no cycles

Step 2: Draw graph with nodes A, B, C, D connected in a loop

A -> B -> D -> C -> A (loop)
Multiple paths between nodes

Why: Graphs allow cycles and multiple connections

Step 3: Try to represent graph loop as a tree

Impossible without breaking tree rules (no cycles)

Why: Trees cannot model loops or multiple parents

Result:

Graph with loop: A -> B -> D -> C -> A
Tree cannot represent this loop

Annotated Code

DSA Typescript

class TreeNode {
  value: string;
  children: TreeNode[];
  constructor(value: string) {
    this.value = value;
    this.children = [];
  }
}

class Graph {
  adjacencyList: Map<string, string[]>;
  constructor() {
    this.adjacencyList = new Map();
  }
  addNode(node: string) {
    if (!this.adjacencyList.has(node)) {
      this.adjacencyList.set(node, []);
    }
  }
  addEdge(node1: string, node2: string) {
    this.adjacencyList.get(node1)?.push(node2);
    this.adjacencyList.get(node2)?.push(node1);
  }
  print() {
    for (const [node, neighbors] of this.adjacencyList.entries()) {
      console.log(`${node} -> ${neighbors.join(', ')}`);
    }
  }
}

// Build tree
const root = new TreeNode('A');
const nodeB = new TreeNode('B');
const nodeC = new TreeNode('C');
root.children.push(nodeB, nodeC);

console.log('Tree structure:');
console.log(`${root.value} -> ${root.children.map(c => c.value).join(', ')}`);

// Build graph
const graph = new Graph();
graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addEdge('A', 'B');
graph.addEdge('B', 'D');
graph.addEdge('D', 'C');
graph.addEdge('C', 'A');

console.log('\nGraph structure:');
graph.print();

root.children.push(nodeB, nodeC);

Add children to root node to form tree structure

graph.addEdge('A', 'B');

Connect nodes A and B in graph

graph.addEdge('B', 'D');

Connect nodes B and D in graph

graph.addEdge('D', 'C');

Connect nodes D and C in graph

graph.addEdge('C', 'A');

Connect nodes C and A in graph to form a cycle

Output

Tree structure:

A -> B, C



Graph structure:

A -> B, C

B -> A, D

C -> D, A

D -> B, C

Complexity Analysis

Time: O(1) for adding nodes and edges because each operation updates fixed references

Space: O(n + e) where n is nodes and e is edges, because graph stores adjacency lists

vs Alternative: Trees use less space and simpler structure but cannot represent cycles or multiple connections like graphs

Edge Cases

Empty tree or graph

No nodes or edges to represent; structures are empty

DSA Typescript

if (!this.adjacencyList.has(node)) { this.adjacencyList.set(node, []); }

Graph with single node and no edges

Graph has one node with empty adjacency list

DSA Typescript

if (!this.adjacencyList.has(node)) { this.adjacencyList.set(node, []); }

When to Use This Pattern

When you need to represent connections that can loop back or have multiple paths between points, use graphs instead of trees because trees cannot model cycles or multiple parents.

Common Mistakes

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

Summary

Graphs represent connections with cycles and multiple paths, unlike trees.

Use graphs when relationships are complex and not strictly hierarchical.

The key insight is that trees are a special kind of graph without cycles or multiple parents.