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

Mental Model

Trees organize data in a way that lets us find and manage things quickly when lists or arrays are too slow or limited.

Analogy: Imagine a family tree or a company chart where each person or role connects to others in branches, making it easy to find relatives or team members without checking everyone one by one.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Tree:
      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Array: [1,2,3,4,5], Linked List: 1->2->3->4->5, Tree: root=1 with children 2 and 3, 2 has children 4 and 5, 3 has child 6

Goal: Show how finding a value or adding new data is slower or limited in arrays and linked lists but easier and faster in trees.

Step 1: Search for value 5 in array by checking each element one by one

[1][2][3][4][5]

Why: Arrays require checking each item until we find the target, which can be slow for large data.

Step 2: Search for value 5 in linked list by moving from head node through each next pointer

1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked lists also require visiting nodes one by one, which is slow for large lists.

Step 3: Search for value 5 in tree by starting at root and choosing branches to follow

      1
     / \
    2   3
   / \   \
  4   5   6

Why: Trees let us skip large parts of data by following branches, making search faster.

Step 4: Add new value 7 as child of node 3 in tree

      1
     / \
    2   3
   / \  / \
  4  5 6  7

Why: Trees allow adding data in structured places without shifting or reordering like arrays.

Result:

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Tree:
      1
     / \
    2   3
   / \  / \
  4  5 6  7

Trees let us find and add data faster and more flexibly than arrays or linked lists.

Annotated Code

DSA Javascript

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  addChild(node) {
    this.children.push(node);
  }
}

// Search in array
function searchArray(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return true;
  }
  return false;
}

// Search in linked list
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
function searchLinkedList(head, target) {
  let curr = head;
  while (curr !== null) {
    if (curr.value === target) return true;
    curr = curr.next;
  }
  return false;
}

// Search in tree
function searchTree(root, target) {
  if (root === null) return false;
  if (root.value === target) return true;
  for (const child of root.children) {
    if (searchTree(child, target)) return true;
  }
  return false;
}

// Driver code
const arr = [1, 2, 3, 4, 5];

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

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);
const node6 = new TreeNode(6);
root.addChild(node2);
root.addChild(node3);
node2.addChild(node4);
node2.addChild(node5);
node3.addChild(node6);

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

// Add new node 7 to tree
const node7 = new TreeNode(7);
node3.addChild(node7);

// Print tree structure simple
function printTree(node, prefix = "") {
  console.log(prefix + node.value);
  for (const child of node.children) {
    printTree(child, prefix + "  ");
  }
}
console.log("Tree structure after adding 7:");
printTree(root);

for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return true; }

Check each array element one by one to find target

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

Traverse linked list nodes sequentially to find target

if (root === null) return false; if (root.value === target) return true; for (const child of root.children) { if (searchTree(child, target)) return true; }

Recursively check tree nodes and their children for target

node3.addChild(node7);

Add new child node to tree without shifting other nodes

Output

Search 5 in array: true

Search 5 in linked list: true

Search 5 in tree: true

Tree structure after adding 7:

1

  2

    4

    5

  3

    6

    7

Complexity Analysis

Time: O(n) for array and linked list search because each element or node must be checked one by one; O(n) for tree search in worst case but often faster due to branch skipping

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

vs Alternative: Arrays and linked lists require linear search which is slow for large data; trees organize data hierarchically allowing faster search and flexible insertion without shifting

Edge Cases

Empty array, linked list, or tree

Search returns false immediately as no elements exist

DSA Javascript

if (root === null) return false;

Searching for value not present

All elements or nodes are checked and search returns false

DSA Javascript

return false;

Adding child to tree node with no children

Child is added successfully as first child

DSA Javascript

this.children.push(node);

When to Use This Pattern

When you need to organize data with parent-child relationships or want faster search and insertion than lists or arrays can provide, reach for trees because they let you skip large parts of data and add nodes flexibly.

Common Mistakes

Mistake: Trying to add elements in the middle of an array or linked list without shifting or updating pointers
Fix: Use trees to add nodes anywhere without shifting by linking children to parents

Summary

Trees organize data hierarchically to allow faster search and flexible insertion.

Use trees when data has natural parent-child relationships or when arrays and linked lists are too slow or limited.

The key insight is that trees let you skip large parts of data and add nodes anywhere without shifting.