Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - Why This Pattern

Mental Model

Trees organize data in a branching way so we can find things faster than just going one by one.

Analogy: Think of a family tree or a company chart where each person or role connects to many others below, making it easy to find someone without checking everyone.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, array: [1, 2, 3, 4, 5], goal: find value 5

Goal: Show how finding a value in a list or array is slower than in a tree structure

Step 1: search value 5 in linked list by checking nodes one by one

1 -> 2 -> 3 -> 4 -> [5] -> null

Why: Linked list requires checking each node until we find 5

Step 2: search value 5 in array by checking elements one by one

[1, 2, 3, 4, 5]

Why: Array also requires checking each element until 5 is found

Step 3: search value 5 in tree by choosing branches

    1
   / \
  2   3
 / \
4  [5]

Why: Tree lets us skip many nodes by following branches, finding 5 faster

Result:

Tree structure: 1 -> 2 -> 5 found faster than linear search in list or array

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Node for linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

// Node for tree
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Search in linked list
bool searchList(ListNode* head, int target) {
    while (head != nullptr) {
        if (head->val == target) return true; // found target
        head = head->next; // move to next node
    }
    return false; // not found
}

// Search in array
bool searchArray(const vector<int>& arr, int target) {
    for (int val : arr) {
        if (val == target) return true; // found target
    }
    return false; // not found
}

// Search in binary tree
bool searchTree(TreeNode* root, int target) {
    if (root == nullptr) return false; // base case: empty node
    if (root->val == target) return true; // found target
    // search left subtree
    if (searchTree(root->left, target)) return true;
    // search right subtree
    return searchTree(root->right, target);
}

int main() {
    // Create linked list 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // Create array [1,2,3,4,5]
    vector<int> arr = {1, 2, 3, 4, 5};

    // Create tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int target = 5;

    cout << "Search in linked list: " << (searchList(head, target) ? "Found" : "Not Found") << endl;
    cout << "Search in array: " << (searchArray(arr, target) ? "Found" : "Not Found") << endl;
    cout << "Search in tree: " << (searchTree(root, target) ? "Found" : "Not Found") << endl;

    return 0;
}

while (head != nullptr) {

traverse linked list nodes one by one

if (head->val == target) return true;

check if current node has target value

for (int val : arr) {

iterate array elements one by one

if (val == target) return true;

check if current array element matches target

if (root == nullptr) return false;

base case: empty tree node means target not found here

if (root->val == target) return true;

check if current tree node has target value

if (searchTree(root->left, target)) return true;

search left subtree recursively

return searchTree(root->right, target);

search right subtree recursively if not found left

Output

Search in linked list: Found

Search in array: Found

Search in tree: Found

Complexity Analysis

Time: O(n) because in worst case we check every element or node once

Space: O(h) for tree search due to recursion stack where h is tree height; O(1) for list and array

vs Alternative: Trees can reduce search time if balanced (O(log n)) unlike linear list or array search which is O(n)

Edge Cases

empty linked list

search returns false immediately

DSA C++

while (head != nullptr) {

empty array

search returns false immediately

DSA C++

for (int val : arr) {

empty tree

search returns false immediately

DSA C++

if (root == nullptr) return false;

When to Use This Pattern

When you need faster search or hierarchical data, think of trees because lists and arrays check items one by one.

Common Mistakes

Mistake: Trying to find a value in a tree without recursion or proper traversal
Fix: Use recursion or a queue/stack to visit nodes systematically

Summary

Trees organize data in branches to speed up search compared to linear lists or arrays.

Use trees when data has hierarchy or when faster search than linear scan is needed.

The key insight is that trees let you skip many elements by following branches, unlike lists or arrays.

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