Tree vs Array vs Linked List When Hierarchy Matters in DSA C - Trade-offs & Analysis

Mental Model

When data has levels or branches, some structures show these connections clearly, while others just list items in order.

Analogy: Think of a family tree (tree) showing parents and children, a photo album (array) showing pictures in order, and a chain of paper clips (linked list) connecting one after another.

Tree:
      A
     / \
    B   C
   /   / \
  D   E   F

Array:
[A][B][C][D][E][F]

Linked List:
A -> B -> C -> D -> E -> F -> null

Dry Run Walkthrough

Input: Data: A family with members A, B, C, D, E, F arranged hierarchically as a tree; also stored as array and linked list.

Goal: Show how hierarchy is clear in tree but not in array or linked list.

Step 1: Represent family as tree with A as root, B and C as children, D child of B, E and F children of C

      A
     / \
    B   C
   /   / \
  D   E   F

Why: Tree shows parent-child links clearly, representing hierarchy.

Step 2: Represent same family as array listing members in order: A, B, C, D, E, F

[A][B][C][D][E][F]

Why: Array stores data in sequence but does not show who is parent or child.

Step 3: Represent same family as linked list connecting nodes A to F in order

A -> B -> C -> D -> E -> F -> null

Why: Linked list shows order but no hierarchy or branching.

Step 4: Try to find children of C in array by scanning elements

[A][B][C][D][E][F]

Why: Array requires extra logic to find hierarchy, no direct links.

Step 5: Try to find children of C in linked list by traversing nodes

A -> B -> C -> D -> E -> F -> null

Why: Linked list traversal is linear and does not show branching.

Result:

Tree:
      A
     / \
    B   C
   /   / \
  D   E   F
Array:
[A][B][C][D][E][F]
Linked List:
A -> B -> C -> D -> E -> F -> null
Hierarchy is clear only in tree.

Annotated Code

DSA C

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

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

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

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

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

// Print tree in preorder to show hierarchy
void printTree(TreeNode* root, int level) {
    if (!root) return;
    for (int i = 0; i < level; i++) printf("  ");
    printf("%c\n", root->val);
    printTree(root->left, level + 1);
    printTree(root->right, level + 1);
}

// Print array
void printArray(char arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("[%c]", arr[i]);
    }
    printf("\n");
}

// Print linked list
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        printf("%c", curr->val);
        if (curr->next) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

int main() {
    // Build tree
    TreeNode* A = newTreeNode('A');
    TreeNode* B = newTreeNode('B');
    TreeNode* C = newTreeNode('C');
    TreeNode* D = newTreeNode('D');
    TreeNode* E = newTreeNode('E');
    TreeNode* F = newTreeNode('F');
    A->left = B;
    A->right = C;
    B->left = D;
    C->left = E;
    C->right = F;

    // Build array
    char arr[] = {'A', 'B', 'C', 'D', 'E', 'F'};

    // Build linked list
    ListNode* head = newListNode('A');
    head->next = newListNode('B');
    head->next->next = newListNode('C');
    head->next->next->next = newListNode('D');
    head->next->next->next->next = newListNode('E');
    head->next->next->next->next->next = newListNode('F');

    printf("Tree (preorder with indentation):\n");
    printTree(A, 0);

    printf("Array: \n");
    printArray(arr, 6);

    printf("Linked List: \n");
    printList(head);

    return 0;
}

A->left = B; A->right = C; B->left = D; C->left = E; C->right = F;

link tree nodes to form hierarchy

for (int i = 0; i < level; i++) printf(" "); printf("%c\n", root->val);

print tree node with indentation to show levels

while (curr) { printf("%c", curr->val); if (curr->next) printf(" -> "); curr = curr->next; }

traverse linked list to print nodes in order

Output

Tree (preorder with indentation):

A

  B

    D

  C

    E

    F

Array: 

[A][B][C][D][E][F]

Linked List: 

A -> B -> C -> D -> E -> F -> null

Complexity Analysis

Time: O(n) because each structure is traversed once to print all elements

Space: O(n) for storing n elements in each structure

vs Alternative: Tree uses extra pointers to show hierarchy, array and linked list store data linearly without hierarchy info

Edge Cases

Empty data (no nodes)

Printing functions handle null or empty inputs gracefully without crashing

DSA C

if (!root) return;

Single element

Tree, array, and linked list all show just one node/item correctly

DSA C

N/A (natural behavior of print functions)

When to Use This Pattern

When a problem involves parent-child or hierarchical relationships, prefer tree structures because arrays and linked lists do not represent branching clearly.

Common Mistakes

Mistake: Using array or linked list to represent hierarchy without extra indexing or pointers
Fix: Use tree nodes with explicit child pointers to represent hierarchy naturally

Summary

Shows how trees represent hierarchy clearly, while arrays and linked lists store data linearly.

Use trees when data has branching or parent-child relationships.

The key insight is that trees have pointers to children, making hierarchy explicit.

Practice

1. Which data structure is best suited to represent hierarchical relationships like a family tree?

easy

A. Stack

B. Array

C. Tree

D. Linked List

Solution

1. Step 1: Understand hierarchy representation

   Hierarchies have parent-child relationships, which trees represent naturally with nodes and branches.

2. Step 2: Compare with other structures

   Arrays and linked lists are linear and do not represent multiple branches from one node easily.

3. Final Answer:

   Tree -> Option C

4. Quick Check:

   Hierarchy = Tree [OK]

Hint: Hierarchy means branching; trees model branching best [OK]

Common Mistakes:

• Choosing array because it stores elements
• Choosing linked list assuming it can represent hierarchy
• Confusing stack with hierarchical structure

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

easy

A. struct Node { int data; struct Node* next; };

B. struct Node { int data; int next; };

C. struct Node { int data; Node next; };

D. struct Node { int data; struct Node next; };

Solution

1. Step 1: Check pointer usage in struct

   A linked list node must have a pointer to the next node, so 'struct Node* next' is correct.

2. Step 2: Identify incorrect declarations

   Options B, C, and D either use wrong types or missing pointers, causing errors.

3. Final Answer:

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

4. Quick Check:

   Pointer to next node = struct Node { int data; struct Node* next; }; [OK]

Hint: Linked list nodes need pointer to next node [OK]

Common Mistakes:

• Using int instead of pointer for next
• Omitting struct keyword in C
• Using struct Node next instead of pointer

3. What will be the output of the following C code that builds a simple 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;
}

medium

A. Garbage value

B. 0

C. Compilation error

D. 10

Solution

1. Step 1: Analyze struct initialization

   The root node is initialized with data=10 and left/right pointers as NULL.

2. Step 2: Check printf output

   Printing root.data will output 10 as assigned.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   root.data = 10 [OK]

Hint: Initialized struct fields print assigned values [OK]

Common Mistakes:

• Assuming uninitialized pointers affect data
• Expecting compilation error due to typedef
• Confusing pointer and value printing

4. Identify the error in this linked list insertion code snippet in C:

struct Node {
  int data;
  struct Node* next;
};

void insertAtFront(struct Node* head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = head;
  head = newNode;
}

medium

A. malloc size is incorrect

B. head is passed by value; changes won't affect original list

C. newNode->next should be NULL

D. Missing free() for old head

Solution

1. Step 1: Understand pointer passing in C

   head is passed by value, so assigning head = newNode only changes local copy.

2. Step 2: Effect on original list

   The original head pointer outside the function remains unchanged, so insertion fails.

3. Final Answer:

   head is passed by value; changes won't affect original list -> Option B

4. Quick Check:

   Pointer passed by value = head is passed by value; changes won't affect original list [OK]

Hint: Pass pointer by reference to modify original list [OK]

Common Mistakes:

• Thinking malloc size is wrong
• Assuming newNode->next must be NULL
• Confusing free() necessity here

5. You need to store a company's organizational chart where each manager can have multiple direct reports. Which data structure is best and why?

hard

A. Tree because it models hierarchical parent-child relationships

B. Linked List because it allows dynamic size

C. Array because it stores elements contiguously

D. Stack because it supports last-in-first-out access

Solution

1. Step 1: Understand organizational chart structure

   It is a hierarchy where managers have multiple direct reports (children).

2. Step 2: Match data structure to hierarchy

   Trees naturally represent such parent-child relationships with multiple branches.

3. Step 3: Evaluate other options

   Arrays and linked lists are linear and do not represent multiple children per node well; stacks are for LIFO access, not hierarchy.

4. Final Answer:

   Tree because it models hierarchical parent-child relationships -> Option A

5. Quick Check:

   Hierarchy with multiple children = Tree [OK]

Hint: Multiple children per node? Use tree structure [OK]

Common Mistakes:

• Choosing array for hierarchy
• Confusing linked list dynamic size with hierarchy
• Using stack for hierarchical data