Time Complexity: Graph vs Tree Key Structural Difference
O(n + e)
0
0
Graph vs Tree Key Structural Difference in DSA Typescript - Complexity Comparison
Understanding Time Complexity
We want to understand how the structure of graphs and trees affects the time it takes to explore them.
How does the shape and rules of these structures change the work needed to visit all parts?
Scenario Under Consideration
Analyze the time complexity of traversing a graph or a tree using Depth-First Search (DFS).
function dfs(node: number, visited: Set, graph: Map): void {
if (visited.has(node)) return;
visited.add(node);
for (const neighbor of graph.get(node) || []) {
dfs(neighbor, visited, graph);
}
}
This code visits all connected nodes starting from one node, exploring neighbors deeply before backtracking.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Recursive calls to visit each node and loop over each node's neighbors.
- How many times: Each node is visited once, and each edge is checked once during traversal.
How Execution Grows With Input
As the number of nodes and edges grows, the work grows roughly with the total connections and points.
| Input Size (n nodes, e edges) | Approx. Operations |
|---|---|
| 10 nodes, 9 edges (tree) | ~19 (10 nodes + 9 edges) |
| 100 nodes, 150 edges (graph) | ~250 (100 nodes + 150 edges) |
| 1000 nodes, 2000 edges (graph) | ~3000 (1000 nodes + 2000 edges) |
Pattern observation: The work grows roughly with the sum of nodes and edges, not just nodes alone.
Final Time Complexity
Time Complexity: O(n + e)
This means the time to explore depends on how many nodes and connections there are combined.
Common Mistake
[X] Wrong: "Traversal time depends only on the number of nodes."
[OK] Correct: Edges (connections) also affect traversal because each connection is checked once, so ignoring edges underestimates the work.
Interview Connect
Understanding how graph and tree structures affect traversal time helps you explain and optimize algorithms clearly in interviews.
Self-Check
"What if the graph is represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"