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

Mental Model

A tree shows clear parent-child links for hierarchy, arrays store items in order without hierarchy, and linked lists chain items linearly without branching.

Analogy: Think of a family tree (tree) showing parents and children, a photo album (array) with pictures in order, and a line of people holding hands (linked list) passing a message one by one.

Tree:
    1
   / \
  2   3
 / \
4   5

Array:
[1][2][3][4][5]

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

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

Goal: Show how hierarchy is represented differently in tree, array, and linked list

Step 1: Look at tree root node 1 with children 2 and 3

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

Why: Tree shows parent 1 connected to children 2 and 3, representing hierarchy

Step 2: Look at node 2 in tree with children 4 and 5

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

Why: Tree shows node 2 has children 4 and 5, deeper hierarchy level

Step 3: Look at array elements in order

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

Why: Array stores elements in sequence but no parent-child links

Step 4: Look at linked list nodes connected linearly

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

Why: Linked list connects nodes one after another without branching

Result:

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

Annotated Code

DSA C++

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

// Tree node definition
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Linked list node definition
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Print tree in preorder to show hierarchy
void printTree(TreeNode* root, int depth = 0) {
    if (!root) return;
    for (int i = 0; i < depth; i++) cout << "  ";
    cout << root->val << endl;
    printTree(root->left, depth + 1);  // go to left child
    printTree(root->right, depth + 1); // go to right child
}

// Print array elements
void printArray(const vector<int>& arr) {
    cout << "Array: ";
    for (int v : arr) cout << v << " ";
    cout << endl;
}

// Print linked list
void printList(ListNode* head) {
    cout << "Linked List: ";
    ListNode* curr = head;
    while (curr) {
        cout << curr->val << " -> ";
        curr = curr->next;  // advance to next node
    }
    cout << "null" << endl;
}

int main() {
    // Build tree
    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);

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

    // Build linked list
    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);

    // Print all
    cout << "Tree (preorder):" << endl;
    printTree(root);
    printArray(arr);
    printList(head);

    return 0;
}

printTree(root);

print tree nodes preorder to show hierarchy with indentation

printArray(arr);

print array elements in order

while (curr) { cout << curr->val << " -> "; curr = curr->next; }

traverse linked list nodes linearly to print values

Output

Tree (preorder):

1

  2

    4

    5

  3

Array: 1 2 3 4 5 

Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 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 pointers to represent hierarchy explicitly, arrays store elements contiguously without hierarchy, linked lists chain nodes linearly without branching; tree traversal is more complex but shows relationships clearly

Edge Cases

Empty tree, array, or linked list

Print functions handle empty structures gracefully by printing nothing or null

DSA C++

if (!root) return; in printTree and while (curr) in printList

Single element structures

Prints single node or element correctly without errors

DSA C++

Base case in printTree and single node handling in printList

When to Use This Pattern

When a problem involves parent-child relationships or hierarchy, use a tree structure; if order matters without hierarchy, use arrays; if you need simple linear traversal with dynamic size, use linked lists.

Common Mistakes

Mistake: Trying to represent hierarchy using arrays or linked lists without extra info
Fix: Use tree nodes with pointers to children to represent hierarchy clearly

Mistake: Confusing linear order with hierarchy
Fix: Remember arrays and linked lists show order, trees show parent-child links

Summary

Shows how trees represent hierarchy with parent-child links, arrays store ordered elements, and linked lists chain nodes linearly.

Use trees when hierarchy matters, arrays for fixed order, and linked lists for flexible linear sequences.

Hierarchy needs explicit links like in trees; arrays and linked lists alone do not show branching relationships.

Practice

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

easy

A. Stack

B. Tree

C. Linked List

D. Array

Solution

1. Step 1: Understand hierarchy representation

   Hierarchical data means elements have parent-child relationships, like a family tree.

2. Step 2: Match data structure to hierarchy

   Trees naturally represent hierarchy with nodes connected to children, unlike arrays or linked lists which are linear.

3. Final Answer:

   Tree -> Option B

4. Quick Check:

   Hierarchy needs Tree [OK]

Hint: Hierarchy means parent-child links, use Tree [OK]

Common Mistakes:

• Choosing Array because it's simple
• Choosing Linked List thinking it's hierarchical
• Confusing Stack with hierarchy

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

easy

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

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

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

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

Solution

1. Step 1: Check pointer usage in struct

   Linked list nodes must point to next node using a pointer type (Node*).

2. Step 2: Validate syntax correctness

   struct Node { int data; Node* next; }; uses Node* next; which is correct pointer syntax. Others have invalid pointer or reference syntax.

3. Final Answer:

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

4. Quick Check:

   Pointer to next node uses Node* [OK]

Hint: Use Node* for next pointer in linked list node [OK]

Common Mistakes:

• Using Node next instead of Node* next
• Using reference Node& which is invalid here
• Incorrect pointer syntax like next*

3. What will be the output of the following C++ code snippet?

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

int main() {
  Node a{1, nullptr};
  Node b{2, &a};
  Node* head = &b;
  while (head) {
    std::cout << head->data << " ";
    head = head->next;
  }
  return 0;
}

medium

A. 1

B. 1 2

C. 2 1

D. 2

Solution

1. Step 1: Understand node linking

   Node b points to a, so list order is b -> a.

2. Step 2: Trace the while loop output

   Prints b.data (2), then a.data (1), then nullptr ends loop.

3. Final Answer:

   2 1 -> Option C

4. Quick Check:

   Linked list prints 2 then 1 [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Assuming order is a then b
• Confusing pointer directions
• Printing only first node

4. Identify the error in this code snippet that tries to create a tree node in C++:

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
};

int main() {
  TreeNode root;
  root.val = 10;
  root.left = nullptr;
  root.right = nullptr;
  root.left->val = 5;
  return 0;
}

medium

A. Dereferencing nullptr in root.left->val

B. Missing semicolon after struct definition

C. Incorrect pointer declaration for left and right

D. root.val should be initialized with new keyword

Solution

1. Step 1: Analyze pointer initialization

   root.left is set to nullptr, so it points to nothing.

2. Step 2: Check pointer dereference

   Accessing root.left->val dereferences nullptr causing runtime error.

3. Final Answer:

   Dereferencing nullptr in root.left->val -> Option A

4. Quick Check:

   Cannot access member via nullptr [OK]

Hint: Never dereference nullptr pointers [OK]

Common Mistakes:

• Ignoring nullptr before dereference
• Thinking struct needs semicolon error
• Confusing pointer declaration syntax

5. You want to store a company's organizational chart where each employee can have multiple subordinates. Which data structure is best and why? A) Array because it stores data contiguously B) Tree because it naturally models multiple children per node C) Linked List because it allows dynamic size D) Stack because it supports last-in-first-out access

hard

A. Tree because it naturally models multiple children per node

B. Array because it stores data contiguously

C. Linked List because it allows dynamic size

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

Solution

1. Step 1: Understand organizational chart structure

   Each employee can have multiple subordinates, forming a hierarchy with multiple children per node.

2. Step 2: Match data structure to hierarchy with multiple children

   Trees allow nodes to have multiple children, perfect for this use case. Arrays and linked lists are linear, stacks are LIFO.

3. Final Answer:

   Tree because it naturally models multiple children per node -> Option A

4. Quick Check:

   Multiple children per node means Tree [OK]

Hint: Multiple children? Use Tree for hierarchy [OK]

Common Mistakes:

• Choosing Array for hierarchy
• Choosing Linked List for multiple children
• Confusing Stack with hierarchical needs