Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Typescript - Performance Analysis

Time Complexity: Why Trees Exist and What Linked Lists and Arrays Cannot Do

O(n) for array search, O(log n) for balanced BST search

Understanding Time Complexity

We want to understand why trees are used instead of just arrays or linked lists.

What makes trees faster or better for some tasks?

Scenario Under Consideration

Analyze the time complexity of searching for a value in different data structures.

// Search in an array
function searchArray(arr: number[], target: number): boolean {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return true;
  }
  return false;
}

// Search in a binary search tree (BST)
function searchBST(node: TreeNode | null, target: number): boolean {
  if (!node) return false;
  if (node.val === target) return true;
  if (target < node.val) return searchBST(node.left, target);
  else return searchBST(node.right, target);
}

This code shows searching for a value in an array and in a binary search tree.

Identify Repeating Operations

Look at what repeats when searching:

• Primary operation: Checking each element in the array or moving down one node in the tree.
• How many times: In array, up to n times (all elements). In tree, up to height h times (nodes from root to leaf).

How Execution Grows With Input

As the number of items grows, how does searching change?

Input Size (n)	Array Search Steps	BST Search Steps (height h)
10	Up to 10 checks	About 4 steps (log2(10))
100	Up to 100 checks	About 7 steps (log2(100))
1000	Up to 1000 checks	About 10 steps (log2(1000))

Pattern observation: Array search grows directly with n, but tree search grows much slower, roughly with the height (log n).

Final Time Complexity

Time Complexity: O(n) for array search, O(log n) for balanced BST search

This means searching in an array takes longer as the list grows, but searching in a balanced tree stays fast even with many items.

Common Mistake

[X] Wrong: "Trees always search faster than arrays no matter what."

[OK] Correct: If the tree is not balanced, its height can be as big as n, making search as slow as array search.

Interview Connect

Understanding why trees exist helps you explain choices in data structures clearly and shows you know how to pick the right tool for the job.

Self-Check

"What if the binary search tree is unbalanced and looks like a linked list? How would the time complexity change?"