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.