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

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

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

Understanding Time Complexity

We want to understand why trees are useful compared to linked lists and arrays.

What problems do trees solve that others cannot do efficiently?

Scenario Under Consideration

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

// Searching in an array
bool searchArray(int arr[], int n, int target) {
  for (int i = 0; i < n; i++) {
    if (arr[i] == target) return true;
  }
  return false;
}

// Searching in a binary search tree
bool searchBST(Node* root, int target) {
  if (!root) return false;
  if (root->val == target) return true;
  if (target < root->val) return searchBST(root->left, target);
  else return searchBST(root->right, target);
}
    

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

Identify Repeating Operations

Look at what repeats when searching.

• Primary operation: Checking each element in array or moving down tree nodes.
• How many times: Array checks up to n times; BST checks up to height of tree times.

How Execution Grows With Input

As input size grows, array search checks more elements one by one.

Input Size (n)	Array Checks	BST Checks (height)
10	Up to 10	Up to 4
100	Up to 100	Up to 7
1000	Up to 1000	Up to 10

Array search grows linearly; BST search grows much slower, roughly with tree height.

Final Time Complexity

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

This means searching in arrays takes longer as size grows, but trees can find items faster by skipping parts.

Common Mistake

[X] Wrong: "Trees are always faster than arrays for searching."

[OK] Correct: If the tree is not balanced, search can be as slow as array search.

Interview Connect

Understanding why trees exist helps you explain data choices 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 does that affect time complexity?"