Tree vs Array vs Linked List When Hierarchy Matters in DSA C++ - Visual Comparison

Concept Flow - Tree vs Array vs Linked List When Hierarchy Matters

Start with Data

↓

Array

↓

Flat

↓

Index

↓

Fast Access

↓

Use Case Decision

This flow shows how data can be organized differently: arrays for flat data, linked lists for linear sequences, and trees for hierarchical relationships.

Execution Sample

DSA C++

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

Node* root = new Node{1, nullptr, nullptr};

This code creates a simple tree node with a value and pointers to left and right children.

Execution Table

Step	Operation	Nodes in Structure	Pointer Changes	Visual State
1	Create root node with value 1	1 node: [1]	root -> Node(1)	[1]
2	Add left child with value 2	2 nodes: [1, 2]	root->left -> Node(2)	[1] | [2]
3	Add right child with value 3	3 nodes: [1, 2, 3]	root->right -> Node(3)	[1] / \ [2] [3]
4	Add left child to node 2 with value 4	4 nodes: [1, 2, 3, 4]	root->left->left -> Node(4)	[1] / \ [2] [3] | [4]
5	Traversal: Visit root	4 nodes	No change	Visiting: [1] / \ [2] [3] | [4]
6	Traversal: Visit left child	4 nodes	No change	Visiting: [2] | [4]
7	Traversal: Visit left-left child	4 nodes	No change	Visiting: [4]
8	Traversal: Visit right child	4 nodes	No change	Visiting: [3]
9	End traversal	4 nodes	No change	Traversal complete

💡 Traversal ends after visiting all nodes in hierarchical order.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
root	nullptr	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)
root->left	nullptr	nullptr	Node(2)	Node(2)	Node(2)	Node(2)
root->right	nullptr	nullptr	nullptr	Node(3)	Node(3)	Node(3)
root->left->left	nullptr	nullptr	nullptr	nullptr	Node(4)	Node(4)

Key Moments - 3 Insights

Why do we use pointers in trees but not in arrays?

Pointers let us link nodes in a flexible hierarchy, shown in execution_table steps 2-4 where left and right pointers connect nodes. Arrays use fixed indexes, so no pointers are needed.

Why can't we represent hierarchy easily with arrays?

Arrays store data linearly with indexes, so they don't show parent-child links. The tree visual state in execution_table steps 3-4 shows how pointers create branches, which arrays lack.

How does traversal visit nodes in a tree?

Traversal follows pointers from parent to children, visiting nodes step-by-step as in execution_table steps 5-8, unlike arrays or linked lists which are linear.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, how many nodes are in the structure?

A 2 nodes

B 3 nodes

C 4 nodes

D 1 node

💡 Hint

Check the 'Nodes in Structure' column at step 3 in execution_table.

At which step does root->left->left pointer get assigned?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look at the 'Pointer Changes' column for when root->left->left is set.

If we replaced the tree with an array, which feature would be missing?

A Fast access by index

B Parent-child hierarchy links

C Linear traversal

D Storing values

💡 Hint

Refer to concept_flow and key_moments about hierarchy representation.

Concept Snapshot

Tree vs Array vs Linked List:
- Arrays store data linearly with indexes.
- Linked Lists store data linearly with pointers to next.
- Trees store data hierarchically with parent-child pointers.
- Use trees when hierarchy matters.
- Arrays are fast for index access.
- Linked lists are easy for insert/delete.
- Trees represent complex relationships clearly.

Full Transcript

This lesson compares trees, arrays, and linked lists focusing on hierarchy. Arrays store data in a flat, indexed way. Linked lists store data linearly with pointers to next nodes. Trees store data hierarchically using parent and child pointers. The example code creates a simple tree with nodes linked by pointers. The execution table shows step-by-step how nodes are added and how traversal visits nodes in order. Variable tracker shows pointer changes after each step. Key moments clarify why pointers are needed for hierarchy and how traversal works. The visual quiz tests understanding of node counts, pointer assignments, and differences between trees and arrays. The snapshot summarizes when to use each structure based on data organization needs.

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