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?"

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees always provide faster access than arrays and linked lists

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees can represent hierarchical relationships which arrays and linked lists cannot

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear order, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow each element to have multiple children, representing hierarchical data like family trees or file systems.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option D

4. Quick Check:

   Hierarchical data needs trees = Because trees can represent hierarchical relationships which arrays and linked lists cannot [OK]

Hint: Trees model hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are simpler to implement
• Believing trees always have faster access

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node* left; Node right; };

D. struct Node { int data; Node left; Node* right; };

Solution

1. Step 1: Understand pointer usage in tree nodes

   Each child node should be a pointer to allow dynamic linking and avoid infinite size.

2. Step 2: Check each option for correct pointer usage

   struct Node { int data; Node* left; Node* right; }; uses pointers for both left and right child nodes, which is correct. Options A, B, and C mix pointers and objects incorrectly.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes must be pointers = struct Node { int data; Node* left; Node* right; }; [OK]

Hint: Child nodes are pointers to avoid infinite size [OK]

Common Mistakes:

• Declaring child nodes as objects causing infinite recursion
• Mixing pointers and objects incorrectly
• Forgetting to use pointers for children

3. Consider this C++ code snippet for a binary tree node and insertion:

struct Node {
  int data;
  Node* left;
  Node* right;
  Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->left->left = new Node(3);

std::cout << root->left->left->data << std::endl;

What will be the output?

medium

A. 5

B. 3

C. 10

D. 15

Solution

1. Step 1: Trace the tree construction

   Root node has value 10. Left child is 5, right child is 15. Left child's left child is 3.

2. Step 2: Identify the printed value

   The code prints root->left->left->data, which is the left child of 5, value 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   root->left->left = 3 [OK]

Hint: Follow pointers step-by-step to find value [OK]

Common Mistakes:

• Confusing left and right children
• Printing root->left->data instead of left->left
• Assuming default values instead of assigned

4. The following code tries to create a binary tree node but causes a compilation error. What is the error?

struct Node {
  int data;
  Node left;
  Node right;
  Node(int val) : data(val) {}
};

int main() {
  Node root(10);
  return 0;
}

medium

A. Error due to missing initialization of left and right nodes

B. Error because constructor syntax is wrong

C. Error because Node contains objects of its own type causing infinite size

D. No error, code compiles fine

Solution

1. Step 1: Analyze struct member types

   Node contains members left and right of type Node (not pointers), causing recursive embedding.

2. Step 2: Understand compilation error cause

   This recursive embedding causes infinite size, which is not allowed by the compiler.

3. Final Answer:

   Error because Node contains objects of its own type causing infinite size -> Option C

4. Quick Check:

   Struct with own type members causes infinite size error [OK]

Hint: Use pointers for self-referential structs to avoid infinite size [OK]

Common Mistakes:

• Thinking constructor syntax is wrong
• Assuming missing initialization causes error
• Believing code compiles fine

5. You want to represent a company's organizational chart where each manager can have multiple direct reports. Why is a tree a better choice than arrays or linked lists for this structure?

hard

A. Because trees allow multiple children per node, representing multiple reports naturally

B. Because arrays can only store numbers, not objects

C. Because linked lists cannot store hierarchical data at all

D. Because trees use less memory than arrays and linked lists

Solution

1. Step 1: Understand the organizational chart structure

   Each manager can have multiple direct reports, which is a hierarchical relationship with branching.

2. Step 2: Compare data structures for representing hierarchy

   Arrays and linked lists are linear and cannot naturally represent multiple children per node, but trees can.

3. Final Answer:

   Trees allow multiple children per node, representing multiple reports naturally -> Option A

4. Quick Check:

   Multiple children per node = trees [OK]

Hint: Multiple children per node? Use trees [OK]

Common Mistakes:

• Thinking arrays cannot store objects
• Believing linked lists cannot store any hierarchy
• Assuming trees always use less memory