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

Mental Model

A tree shows clear parent-child links for hierarchy, arrays list items flatly, and linked lists chain items linearly.

Analogy: Think of a family tree (tree) showing generations, a photo album (array) showing pictures side by side, and a treasure map path (linked list) showing one step after another.

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 each structure represents hierarchy and order differently

Step 1: Look at the 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: Observe children of node 2 in tree: nodes 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 deeper hierarchy with 4 and 5 as children of 2, unlike flat array or linear list

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 flatly without parent-child links, just positions

Step 4: Follow linked list nodes from 1 to 5

Tree:
    1
   / \
  2   3
 / \
4   5

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

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

Why: Linked list shows linear order but no branching hierarchy

Result:

Tree:
    1
   / \
  2   3
 / \
4   5

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

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

Annotated Code

DSA Typescript

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

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

// Build tree
function buildTree(): TreeNode {
  const root = new TreeNode(1);
  const node2 = new TreeNode(2);
  const node3 = new TreeNode(3);
  const node4 = new TreeNode(4);
  const node5 = new TreeNode(5);
  root.children.push(node2, node3); // root has children 2 and 3
  node2.children.push(node4, node5); // node 2 has children 4 and 5
  return root;
}

// Print tree in simple indented form
function printTree(node: TreeNode, indent = ""): void {
  console.log(indent + node.value);
  for (const child of node.children) {
    printTree(child, indent + "  ");
  }
}

// Build array
function buildArray(): number[] {
  return [1, 2, 3, 4, 5];
}

// Print array
function printArray(arr: number[]): void {
  console.log(arr.map(x => `[${x}]`).join(''));
}

// Build linked list
function buildLinkedList(): LinkedListNode {
  const head = new LinkedListNode(1);
  let current = head;
  for (let val = 2; val <= 5; val++) {
    current.next = new LinkedListNode(val);
    current = current.next; // advance to next node
  }
  return head;
}

// Print linked list
function printLinkedList(head: LinkedListNode | null): void {
  let curr = head;
  let output = '';
  while (curr !== null) {
    output += curr.value + ' -> ';
    curr = curr.next; // move to next node
  }
  output += 'null';
  console.log(output);
}

// Driver
const treeRoot = buildTree();
console.log('Tree:');
printTree(treeRoot);

const arr = buildArray();
console.log('\nArray:');
printArray(arr);

const linkedListHead = buildLinkedList();
console.log('\nLinked List:');
printLinkedList(linkedListHead);

root.children.push(node2, node3); // root has children 2 and 3

link children nodes to root to build hierarchy

node2.children.push(node4, node5); // node 2 has children 4 and 5

add children to node 2 to deepen hierarchy

current.next = new LinkedListNode(val);

link new node to current tail to build linear chain

curr = curr.next; // move to next node

advance pointer to next node to traverse linked list

Output

Tree:

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 built or printed by visiting each element once

Space: O(n) because all structures store n elements explicitly

vs Alternative: Tree uses extra space for child pointers but shows hierarchy clearly; array uses contiguous space but no hierarchy; linked list uses pointers but only linear order

Edge Cases

Empty tree, array, or linked list

Print functions handle empty inputs gracefully without errors

DSA Typescript

while (curr !== null) { ... } in printLinkedList prevents null pointer errors

Single node/tree with one element

Structures show just one element with no children or next nodes

DSA Typescript

for (const child of node.children) { ... } in printTree handles zero children

When to Use This Pattern

When a problem needs to represent parent-child relationships or hierarchy, use a tree; for simple ordered collections, use arrays or linked lists.

Common Mistakes

Mistake: Trying to represent hierarchy using only arrays or linked lists without extra info
Fix: Use tree nodes with child pointers to capture hierarchy explicitly

Summary

Shows how trees represent hierarchy, arrays store flat lists, and linked lists chain items linearly.

Use trees when parent-child relationships matter, arrays for indexed access, and linked lists for linear sequences.

The key is that trees have branching pointers to children, arrays have fixed positions, and linked lists have next pointers forming a chain.

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