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

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

Start: Need to store data with hierarchy

↓

Choose Data Structure Type

↓

Array

↓

Flat list

↓

No hierarchy

↓

Limited for hierarchy

This flow shows how choosing between array, linked list, and tree depends on whether hierarchy matters in data storage.

Execution Sample

DSA Typescript

class TreeNode {
  value: number;
  children: TreeNode[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

Defines a tree node with a value and a list of children to represent hierarchy.

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 child node with value 2 to root	2 nodes: [1, 2]	root.children[0] -> node(2)	1 └─ 2
3	Add child node with value 3 to root	3 nodes: [1, 2, 3]	root.children[1] -> node(3)	1 ├─ 2 └─ 3
4	Add child node with value 4 to node 2	4 nodes: [1, 2, 3, 4]	node(2).children[0] -> node(4)	1 ├─ 2 │ └─ 4 └─ 3
5	Compare with array storing [1, 2, 3, 4]	4 elements: [1, 2, 3, 4]	No pointers, flat structure	[1, 2, 3, 4]
6	Compare with linked list storing 1 -> 2 -> 3 -> 4	4 nodes: 1 -> 2 -> 3 -> 4	Pointers: node1.next -> node2, node2.next -> node3, node3.next -> node4	1 -> 2 -> 3 -> 4 -> null
7	Hierarchy matters: tree shows parent-child clearly	4 nodes in tree	Pointers show children per node	1 ├─ 2 │ └─ 4 └─ 3
8	Hierarchy matters: array and linked list show flat or linear only	4 elements/nodes	No parent-child pointers	Array: [1, 2, 3, 4] Linked List: 1 -> 2 -> 3 -> 4 -> null
9	End comparison	Structures built	Pointers set as above	Tree best for hierarchy

💡 Comparison ends after showing how tree, array, and linked list represent hierarchy differently.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
root	null	node(1)	node(1)	node(1)	node(1)	node(1)
root.children	[]	[]	[node(2)]	[node(2), node(3)]	[node(2), node(3)]	[node(2), node(3)]
node(2).children	[]	[]	[]	[]	[node(4)]	[node(4)]
array	[]	[1]	[1, 2]	[1, 2, 3]	[1, 2, 3, 4]	[1, 2, 3, 4]
linkedList	null	1 -> null	1 -> 2 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> null

Key Moments - 3 Insights

Why can't arrays show parent-child relationships clearly?

Arrays store elements in a flat sequence without pointers to children, so they cannot represent hierarchy as shown in execution_table rows 5 and 8.

Why is a tree better than a linked list when hierarchy matters?

Trees have nodes with multiple children pointers, allowing parent-child links, unlike linked lists which only have a single next pointer, as seen in execution_table rows 6 and 7.

How does adding a child to a tree node change the structure?

Adding a child updates the parent's children array pointer, creating a visible branch in the tree structure, shown in execution_table rows 2, 3, and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the tree?

A 1 ├─ 2 │ └─ 4 └─ 3

B 1 -> 2 -> 3 -> 4 -> null

C [1, 2, 3, 4]

D 1 └─ 2 └─ 3 └─ 4

💡 Hint

Check the Visual State column at step 4 in execution_table.

At which step does the linked list reach 1 -> 2 -> 3 -> 4 -> null?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the Pointer Changes and Visual State columns for linked list in execution_table.

If we remove node 4 from the tree, how would the variable_tracker change for node(2).children?

A It remains [node(4)]

B It becomes null

C It becomes [] after removal

D It becomes [node(3)]

💡 Hint

Refer to variable_tracker row for node(2).children and think about removing the child node.

Concept Snapshot

Tree vs Array vs Linked List when hierarchy matters:
- Array: flat list, no hierarchy pointers
- Linked List: linear nodes with next pointer
- Tree: nodes with multiple children pointers
- Use tree to represent parent-child relationships clearly
- Arrays and linked lists are limited for hierarchical data

Full Transcript

This lesson compares tree, array, and linked list data structures focusing on how they represent hierarchy. Arrays store data in a flat sequence without pointers, so they cannot show parent-child relationships. Linked lists connect nodes linearly with a single next pointer, which also limits hierarchy representation. Trees have nodes with multiple children pointers, allowing clear parent-child links. The execution table shows step-by-step building of a tree with nodes 1, 2, 3, and 4, and compares it to arrays and linked lists storing the same values. Variable tracking shows how pointers and children arrays change as nodes are added. Key moments clarify why trees are best for hierarchical data and how adding children changes the structure. Visual quizzes test understanding of tree structure visualization, linked list state, and effects of removing nodes. The quick snapshot summarizes when to use each structure based on hierarchy needs.

Practice

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

easy

A. Tree

B. Array

C. Linked List

D. Stack

Solution

1. Step 1: Understand hierarchy representation

   Hierarchies have parent-child relationships, which are naturally modeled by trees.

2. Step 2: Compare data structures

   Arrays and linked lists are linear and do not represent branching well, unlike trees.

3. Final Answer:

   Tree -> Option A

4. Quick Check:

   Hierarchy = Tree [OK]

Hint: Hierarchy means branching, so choose Tree [OK]

Common Mistakes:

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

2. Which of the following is the correct TypeScript syntax to declare a simple linked list node with a value and a next pointer?

easy

A. class Node { value: number; next: Node; constructor(value: number) { this.value = value; this.next = null; } }

B. class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } }

C. class Node { value: number; next: null; constructor(value: number) { this.value = value; this.next = null; } }

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check next pointer type

   Next pointer should allow either another Node or null to mark list end.

2. Step 2: Verify constructor initialization

   Constructor sets value and initializes next to null correctly.

3. Final Answer:

   class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } -> Option B

4. Quick Check:

   Next pointer = Node or null [OK]

Hint: Next pointer must allow null for list end [OK]

Common Mistakes:

• Not allowing null for next pointer
• Initializing next as undefined instead of null
• Using any type which loses type safety

3. Given the following TypeScript code, what will be the printed output?

class TreeNode {
  value: number;
  children: TreeNode[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
root.children.push(child1, child2);
console.log(root.children.map(c => c.value));

medium

A. [1, 2, 3]

B. Error: children is not iterable

C. [[2], [3]]

D. [2, 3]

Solution

1. Step 1: Understand tree structure

   Root node has value 1 and two children with values 2 and 3.

2. Step 2: Analyze console.log output

   Mapping children array extracts values [2, 3], root's value 1 is not included.

3. Final Answer:

   [2, 3] -> Option D

4. Quick Check:

   Children values = [2, 3] [OK]

Hint: Mapping children prints their values, not root's [OK]

Common Mistakes:

• Including root value in output
• Expecting nested arrays instead of flat array
• Assuming children is not iterable

4. Identify the bug in this TypeScript code that tries to create a linked list and print its values:

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

let current = head;
while (current !== null) {
  console.log(current.value);
  current = current.next.next;
}

medium

A. Using console.log inside loop is invalid

B. Incorrect constructor syntax

C. Accessing next.next without checking if next is null

D. Node class missing a previous pointer

Solution

1. Step 1: Trace the while loop iteration

   Loop moves current by current.next.next, skipping nodes and risking null access.

2. Step 2: Identify null pointer risk

   When current.next is null, accessing current.next.next causes runtime error.

3. Final Answer:

   Accessing next.next without checking if next is null -> Option C

4. Quick Check:

   Null check missing before next.next access [OK]

Hint: Always check next before accessing next.next [OK]

Common Mistakes:

• Ignoring null checks causing runtime errors
• Thinking constructor syntax is wrong
• Believing console.log causes errors

5. You need to represent a company's organizational chart where each employee can have multiple direct reports. Which data structure should you use and why? Choose the best option and explain your reasoning.

hard

A. Tree, because it naturally models hierarchical relationships with multiple children

B. Linked List, because it allows dynamic insertion and deletion of employees

C. Stack, because it supports last-in-first-out operations suitable for reporting

D. Array, because it stores elements in order and is easy to access by index

Solution

1. Step 1: Analyze the problem requirements

   Organizational chart has hierarchy with employees having multiple direct reports (children).

2. Step 2: Match data structure to hierarchy

   Tree structure supports nodes with multiple children, representing managers and their reports well.

3. Step 3: Evaluate other options

   Array and linked list are linear and do not represent branching; stack is for LIFO, not hierarchy.

4. Final Answer:

   Tree, because it naturally models hierarchical relationships with multiple children -> Option A

5. Quick Check:

   Hierarchy with multiple children = Tree [OK]

Hint: Hierarchy with multiple children means Tree is best [OK]

Common Mistakes:

• Choosing Array for hierarchy
• Thinking Linked List handles multiple children well
• Confusing Stack with hierarchical data