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.