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

Mental Model

Trees let us organize data in a way that is faster to search and flexible to grow, unlike simple lists or arrays.

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

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Tree:
       1
      / \
     2   3
    / \
   4   5

Dry Run Walkthrough

Input: Array: [1,2,3,4,5], Linked List: 1->2->3->4->5, Tree with root 1 and children 2,3; 2 has children 4,5

Goal: Show how searching for value 5 differs in time and steps between array, linked list, and tree

Step 1: Search for 5 in array by checking each element from start

[1][2][3][4][5]

Why: Arrays require checking elements one by one if unsorted

Step 2: Check elements 1, 2, 3, 4, then 5 in array

[1][2][3][4][5]

Why: Must scan all elements until 5 is found

Step 3: Search for 5 in linked list by moving from head node to next until found

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

Why: Linked lists also require linear search

Step 4: Traverse nodes 1, 2, 3, 4, then 5 in linked list

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

Why: Must follow pointers one by one

Step 5: Search for 5 in tree by starting at root 1, then go to child 2, then child 5

       1
      / \
     2   3
    / \
   4   5 ↑

Why: Trees let us skip large parts by branching

Result:

Array and linked list require checking 5 elements; tree finds 5 in 3 steps by branching

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Tree node structure
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Create new tree node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Search in array
int searchArray(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// Linked list node
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// Create new list node
ListNode* newListNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Search in linked list
int searchList(ListNode* head, int target) {
    int index = 0;
    ListNode* curr = head;
    while (curr != NULL) {
        if (curr->val == target) return index;
        curr = curr->next;
        index++;
    }
    return -1;
}

// Search in tree (DFS)
int searchTree(TreeNode* root, int target) {
    if (root == NULL) return 0;
    if (root->val == target) return 1;
    if (searchTree(root->left, target)) return 1;
    if (searchTree(root->right, target)) return 1;
    return 0;
}

int main() {
    int arr[] = {1,2,3,4,5};
    int size = 5;
    int target = 5;

    // Linked list setup: 1->2->3->4->5
    ListNode* head = newListNode(1);
    head->next = newListNode(2);
    head->next->next = newListNode(3);
    head->next->next->next = newListNode(4);
    head->next->next->next->next = newListNode(5);

    // Tree setup:
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    int arrIndex = searchArray(arr, size, target);
    int listIndex = searchList(head, target);
    int foundInTree = searchTree(root, target);

    printf("Array search index: %d\n", arrIndex);
    printf("Linked list search index: %d\n", listIndex);
    printf("Tree search found: %s\n", foundInTree ? "Yes" : "No");

    return 0;
}

for (int i = 0; i < size; i++) { if (arr[i] == target) return i; }

linear search through array elements

while (curr != NULL) { if (curr->val == target) return index; curr = curr->next; index++; }

linear traversal through linked list nodes

if (root == NULL) return 0; if (root->val == target) return 1; if (searchTree(root->left, target)) return 1; if (searchTree(root->right, target)) return 1;

recursive depth-first search in tree nodes

Output

Array search index: 4

Linked list search index: 4

Tree search found: Yes

Complexity Analysis

Time: O(n) for array and linked list because each element/node is checked one by one; O(n) for tree in worst case but often faster due to branching

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

vs Alternative: Trees allow faster search by skipping large parts of data via branches, unlike arrays and linked lists which require linear scanning

Edge Cases

Empty array, linked list, or tree

Search returns -1 for array and list, 0 (not found) for tree

DSA C

if (root == NULL) return 0;

Target not present in data structures

Search returns -1 for array and list, 0 for tree

DSA C

return -1; in array and list search functions

Single element structures with target present

Search returns index 0 for array and list, 1 (found) for tree

DSA C

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

When to Use This Pattern

When you need to organize data for faster search or hierarchical relationships, think of trees because arrays and linked lists require checking every item one by one.

Common Mistakes

Mistake: Assuming arrays or linked lists can efficiently represent hierarchical data
Fix: Use trees to represent data with parent-child relationships for faster search and flexible structure

Summary

Trees organize data hierarchically to enable faster search and flexible growth.

Use trees when data has natural parent-child relationships or when fast search is needed.

The key insight is that trees let you skip large parts of data by branching, unlike arrays or linked lists that require linear scanning.

Practice

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

easy

A. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide.

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 always have faster access time than arrays and linked lists.

Solution

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

   Arrays and linked lists store data linearly, which makes representing hierarchical relationships difficult and inefficient.

2. Step 2: Identify the advantage of trees

   Trees naturally represent hierarchical data with parent-child relationships, allowing efficient searching and organization of such data.

3. Final Answer:

   Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide. -> Option A

4. Quick Check:

   Hierarchical data needs trees = A [OK]

Hint: Trees handle 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 time

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

easy

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

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

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

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

Solution

1. Step 1: Check struct declaration syntax in C

   In C, to declare a struct with pointers to itself, use 'struct Node*' for left and right child pointers.

2. Step 2: Validate typedef usage

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; correctly defines the struct and typedefs it as Node for easy use.

3. Final Answer:

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

4. Quick Check:

   Correct self-referential struct syntax = B [OK]

Hint: Use 'struct Node*' for child pointers in C structs [OK]

Common Mistakes:

• Using 'Node*' inside struct before typedef
• Declaring child nodes as struct instead of pointers
• Incorrect typedef syntax

3. Consider the following C code that creates a simple binary tree node and prints its data:

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int main() {
  Node root = {10, NULL, NULL};
  printf("%d", root.data);
  return 0;
}

What is the output of this program?

medium

A. Compilation error

B. 0

C. Garbage value

D. 10

Solution

1. Step 1: Analyze struct initialization

   The root node is initialized with data = 10 and both children as NULL pointers.

2. Step 2: Check printf output

   Printing root.data will output 10 as it is explicitly set.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Initialized data printed = 10 [OK]

Hint: Initialized struct fields print their values directly [OK]

Common Mistakes:

• Assuming uninitialized fields print garbage
• Confusing pointer NULL with data value
• Expecting compilation error due to struct

4. The following C code attempts to create a binary tree node but has an error:

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int main() {
  Node* root;
  root->data = 5;
  root->left = NULL;
  root->right = NULL;
  return 0;
}

What is the error and how to fix it?

medium

A. root is uninitialized pointer; fix by allocating memory with malloc.

B. root should be a struct, not a pointer; fix by declaring 'Node root;' instead.

C. Missing semicolon after struct definition; add semicolon.

D. Cannot assign NULL to pointers; use 0 instead.

Solution

1. Step 1: Identify pointer initialization issue

   root is declared as a pointer but not assigned memory, so accessing root->data causes undefined behavior.

2. Step 2: Fix by allocating memory

   Use malloc to allocate memory before accessing members: root = malloc(sizeof(Node));

3. Final Answer:

   root is uninitialized pointer; fix by allocating memory with malloc. -> Option A

4. Quick Check:

   Pointer must point to allocated memory = C [OK]

Hint: Always malloc before using pointer to struct [OK]

Common Mistakes:

• Using pointer without allocation
• Confusing pointer and struct variable
• Ignoring memory allocation errors

5. You want to represent a company's organizational chart where each manager can have multiple employees reporting to them. Why is a tree a better data structure than arrays or linked lists for this, and how would you implement it in C?

hard

A. Arrays are better because they allow random access; implement with a large array of employees.

B. Trees represent hierarchical relationships naturally; implement using nodes with data and a list of child pointers.

C. Linked lists are better because they are simple; implement with a single linked list of all employees.

D. Trees are not suitable; use hash tables instead for fast lookup.

Solution

1. Step 1: Understand the hierarchical nature of organizational charts

   Each manager can have multiple employees, forming a tree-like structure with parent-child relationships.

2. Step 2: Compare data structures for this use case

   Arrays and linked lists are linear and cannot represent multiple children per node efficiently; trees allow multiple children per node naturally.

3. Step 3: Implementation approach in C

   Use a struct with data and a dynamic array or linked list of pointers to child nodes to represent multiple employees under a manager.

4. Final Answer:

   Trees represent hierarchical relationships naturally; implement using nodes with data and a list of child pointers. -> Option B

5. Quick Check:

   Hierarchy needs trees with child lists = A [OK]

Hint: Use trees with child lists for multi-level hierarchy [OK]

Common Mistakes:

• Trying to use arrays for hierarchical data
• Using single linked list for multi-child nodes
• Ignoring the need for multiple children pointers