Tree vs Array vs Linked List When Hierarchy Matters in DSA Typescript - Complexity Comparison

Time Complexity: Tree vs Array vs Linked List When Hierarchy Matters

O(n)

Understanding Time Complexity

When working with data that has a hierarchy, like family trees or company structures, choosing the right data structure matters.

We want to understand how fast we can find or visit elements depending on the structure used.

Scenario Under Consideration

Analyze the time complexity of traversing hierarchical data stored in different structures.

// Tree node definition
class TreeNode {
  value: number;
  children: TreeNode[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

// Function to traverse tree
function traverseTree(node: TreeNode | null): void {
  if (!node) return;
  console.log(node.value);
  for (const child of node.children) {
    traverseTree(child);
  }
}
    

This code visits every node in a tree, printing its value and then visiting its children recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the time to visit all nodes grows proportionally.

Input Size (n nodes)	Approx. Operations (visits)
10	10
100	100
1000	1000

Pattern observation: The time grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means visiting all nodes takes time proportional to the number of nodes.

Common Mistake

[X] Wrong: "Using an array or linked list to represent hierarchy is always faster."

[OK] Correct: Arrays and linked lists do not naturally represent parent-child links, so finding children can take extra time, making traversal slower.

Interview Connect

Understanding how different structures handle hierarchy helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

"What if we stored the hierarchy in a flat array with parent indexes? How would the time complexity of traversal change?"