Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Typescript - Why This Pattern

Mental Model

Trees organize data in a branching way so we can find things faster than just going one by one.

Analogy: Imagine a family tree or a company chart where each person has children or team members. You can quickly jump to a group instead of checking everyone one by one.

      Root
      /  \
    A      B
   / \    / \
  C   D  E   F

Dry Run Walkthrough

Input: We want to find a name in a list of 7 people: [Alice, Bob, Carol, Dave, Eve, Frank, Grace]. Using an array, linked list, and tree.

Goal: Show why trees help find data faster than arrays or linked lists when data grows.

Step 1: Search for 'Eve' in an array by checking each item one by one.

[Alice] -> [Bob] -> [Carol] -> [Dave] -> [Eve] -> [Frank] -> [Grace]

Why: Arrays require checking each element until we find the target.

Step 2: Search for 'Eve' in a linked list by moving from head to next node until found.

Head -> Alice -> Bob -> Carol -> Dave -> Eve -> Frank -> Grace -> null

Why: Linked lists also require sequential checking, no shortcuts.

Step 3: Search for 'Eve' in a tree by starting at root and choosing branches.

Root -> B -> Eve

Why: Trees let us skip many nodes by choosing branches, reducing checks.

Result:

Tree search path: Root -> B -> Eve
Found 'Eve' faster than array or linked list.

Annotated Code

DSA Typescript

class TreeNode {
  value: string;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(value: string) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function searchArray(arr: string[], target: string): boolean {
  for (const item of arr) {
    if (item === target) return true;
  }
  return false;
}

class ListNode {
  value: string;
  next: ListNode | null;
  constructor(value: string) {
    this.value = value;
    this.next = null;
  }
}

function searchLinkedList(head: ListNode | null, target: string): boolean {
  let current = head;
  while (current !== null) {
    if (current.value === target) return true;
    current = current.next;
  }
  return false;
}

function searchTree(root: TreeNode | null, target: string): boolean {
  if (root === null) return false;
  if (root.value === target) return true;
  return searchTree(root.left, target) || searchTree(root.right, target);
}

// Driver code
const arr = ["Alice", "Bob", "Carol", "Dave", "Eve", "Frank", "Grace"];

const head = new ListNode("Alice");
head.next = new ListNode("Bob");
head.next.next = new ListNode("Carol");
head.next.next.next = new ListNode("Dave");
head.next.next.next.next = new ListNode("Eve");
head.next.next.next.next.next = new ListNode("Frank");
head.next.next.next.next.next.next = new ListNode("Grace");

const root = new TreeNode("Root");
root.left = new TreeNode("A");
root.right = new TreeNode("B");
root.left.left = new TreeNode("C");
root.left.right = new TreeNode("D");
root.right.left = new TreeNode("Eve");
root.right.right = new TreeNode("F");

console.log("Search 'Eve' in array:", searchArray(arr, "Eve"));
console.log("Search 'Eve' in linked list:", searchLinkedList(head, "Eve"));
console.log("Search 'Eve' in tree:", searchTree(root, "Eve"));

for (const item of arr) { if (item === target) return true; }

Check each array element one by one until target found

while (current !== null) { if (current.value === target) return true; current = current.next; }

Traverse linked list nodes sequentially until target found

if (root === null) return false; if (root.value === target) return true; return searchTree(root.left, target) || searchTree(root.right, target);

Recursively check tree nodes, branching left and right to find target

Output

Search 'Eve' in array: true

Search 'Eve' in linked list: true

Search 'Eve' in tree: true

Complexity Analysis

Time: O(n) for array and linked list because each element/node may be checked once; O(n) worst case for tree but often faster due to branching

Space: O(1) for array and linked list search; O(h) for tree search due to recursion stack where h is tree height

vs Alternative: Trees can reduce search time by skipping large parts of data, unlike arrays and linked lists which check sequentially

Edge Cases

Empty array, linked list, or tree

Search returns false immediately

DSA Typescript

if (root === null) return false;

Target not present in data structure

Search completes full traversal and returns false

DSA Typescript

return false;

Single element data structure with target present

Search returns true immediately

DSA Typescript

if (item === target) return true;

When to Use This Pattern

When you need faster search or hierarchical data representation beyond simple lists or arrays, think of trees because they let you skip large parts of data.

Common Mistakes

Mistake: Trying to use arrays or linked lists for hierarchical data causing slow searches
Fix: Use trees to organize data in branches for faster access

Summary

Trees organize data in branches to speed up search and represent hierarchy.

Use trees when data has natural parent-child relationships or when fast search is needed.

The key is that trees let you jump over many items by choosing branches instead of checking one by one.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees are easier to implement than arrays and linked lists.

B. Because trees use less memory than arrays and linked lists.

C. Because trees always have faster access times than arrays and linked lists.

D. Because trees can represent hierarchical relationships which arrays and linked lists cannot.

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data in a linear sequence, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow each element to have multiple children, representing hierarchical data like file systems or organization charts.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option D

4. Quick Check:

   Hierarchical data needs trees = C [OK]

Hint: Trees model hierarchies; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Believing trees are simpler to implement
• Assuming trees always have faster access

2. Which of the following is the correctly way to declare a simple tree node in TypeScript?

easy

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

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

C. class TreeNode { value: number; prev: TreeNode; constructor(value: number) { this.value = value; this.prev = null; } }

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

Solution

1. Step 1: Identify tree node properties

   A tree node stores a value and multiple children nodes, so it needs a children array.

2. Step 2: Match with the correct class declaration

   class TreeNode { value: number; children: TreeNode[]; constructor(value: number) { this.value = value; this.children = []; } } declares a value and children array, suitable for a tree node. Declarations using next or prev are for linked lists. class TreeNode { value: number; array: number[]; constructor(value: number) { this.value = value; this.array = []; } } uses an array of numbers, not nodes.

3. Final Answer:

   correctly declares a tree node with children array -> Option A

4. Quick Check:

   Tree nodes have children array = A [OK]

Hint: Tree nodes have children arrays, not next or prev pointers [OK]

Common Mistakes:

• Confusing tree nodes with linked list nodes
• Using next or prev instead of children array
• Using array of numbers instead of nodes

3. What will be the output of the following TypeScript code?

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);
root.children.push(child2);
console.log(root.children.length);

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Understand the tree construction

   A root node with value 1 is created. Two child nodes with values 2 and 3 are created and added to root's children array.

2. Step 2: Count the children of root

   Two children are pushed into root.children, so root.children.length is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Two children added = 2 [OK]

Hint: Count how many children are pushed into the children array [OK]

Common Mistakes:

• Assuming children length is 0 by default
• Confusing children with linked list next pointers
• Counting nodes instead of children array length

4. Find the error in this TypeScript code that tries to create a tree node and add children:

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

const root = new TreeNode(10);
root.children.push(new TreeNode(20));

medium

A. The constructor should not have parameters.

B. children should be initialized as an empty array, not null.

C. The push method does not exist on arrays.

D. TreeNode class should not have a children property.

Solution

1. Step 1: Check children initialization

   children is set to null, so calling push on null causes an error.

2. Step 2: Correct children initialization

   children should be initialized as an empty array [] to allow push method calls.

3. Final Answer:

   children should be initialized as an empty array, not null -> Option B

4. Quick Check:

   push on null causes error = A [OK]

Hint: Initialize children as [] before pushing nodes [OK]

Common Mistakes:

• Setting children to null instead of []
• Trying to push on null causing runtime error
• Ignoring constructor parameters

5. You want to represent a company's organizational chart where each employee can have multiple subordinates. Which data structure is best and why?

Choose the best answer.

hard

A. Use a tree because it naturally models hierarchical relationships with multiple children per node.

B. Use a linked list because it allows easy insertion and deletion of employees.

C. Use a stack because it follows last-in-first-out which suits organizational charts.

D. Use an array because it stores data sequentially and is easy to access.

Solution

1. Step 1: Understand the problem context

   An organizational chart is hierarchical: managers have multiple subordinates, forming branches.

2. Step 2: Match data structure to hierarchy

   Trees allow nodes to have multiple children, perfectly modeling this hierarchy. Arrays and linked lists are linear, stacks are LIFO structures unsuitable here.

3. Final Answer:

   Use a tree because it naturally models hierarchical relationships -> Option A

4. Quick Check:

   Hierarchy needs trees = D [OK]

Hint: Hierarchies need trees, not linear or LIFO structures [OK]

Common Mistakes:

• Choosing arrays or linked lists for hierarchical data
• Confusing stack behavior with organizational needs
• Ignoring multiple children per node requirement