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.

Practice

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

easy

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

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

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

D. Because trees always store data in sorted order unlike arrays and linked lists.

Solution

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

   Arrays and linked lists store data linearly, so they cannot naturally represent parent-child or hierarchical relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow nodes 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 A

4. Quick Check:

   Hierarchy needs trees = B [OK]

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

Common Mistakes:

• Thinking trees use less memory than arrays
• Believing trees are simpler to implement
• Assuming trees always store sorted data

2. Which of the following is the correct way to create a simple tree node object in JavaScript?

easy

A. const node = new TreeNode(5, []);

B. const node = { value: 5, children: [] };

C. const node = (value: 5, children: []);

D. const node = [5, []];

Solution

1. Step 1: Recall JavaScript object syntax

   Objects use curly braces with key-value pairs, like { key: value }.

2. Step 2: Check each option

   const node = { value: 5, children: [] }; uses correct object syntax with keys 'value' and 'children'. const node = [5, []]; is an array, not an object. const node = (value: 5, children: []); uses invalid syntax. const node = new TreeNode(5, []); assumes a class TreeNode which is not defined.

3. Final Answer:

   const node = { value: 5, children: [] }; -> Option B

4. Quick Check:

   JS object syntax = D [OK]

Hint: JS objects use curly braces with key-value pairs [OK]

Common Mistakes:

• Using array syntax instead of object
• Using invalid parentheses syntax
• Assuming class exists without definition

3. What will be the output of the following code that creates a simple tree and prints the root's first child's value?

const root = { value: 1, children: [ { value: 2, children: [] }, { value: 3, children: [] } ] };
console.log(root.children[0].value);

medium

A. undefined

B. 1

C. 3

D. 2

Solution

1. Step 1: Understand the tree structure

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

2. Step 2: Access the first child's value

   root.children[0] refers to the first child node with value 2, so root.children[0].value is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   root.children[0].value = 2 [OK]

Hint: Index 0 child value is root.children[0].value [OK]

Common Mistakes:

• Printing root.value instead of child's
• Using wrong index for children
• Confusing children array with object

4. Find the error in this code that tries to add a child node to a tree:

const root = { value: 10, children: [] };
root.children.push({ value: 20 });
console.log(root.children[0].value);

medium

A. The root node should not have a 'children' property.

B. The push method cannot be used on arrays.

C. The child node is missing the 'children' array property.

D. The console.log syntax is incorrect.

Solution

1. Step 1: Check the child node structure

   The child node added has only 'value' but no 'children' array, which breaks the tree node structure.

2. Step 2: Understand tree node consistency

   Each node should have a 'children' property as an array, even if empty, to maintain uniformity.

3. Final Answer:

   The child node is missing the 'children' array property. -> Option C

4. Quick Check:

   Missing children array in child node = A [OK]

Hint: Every tree node needs a children array [OK]

Common Mistakes:

• Thinking push is invalid on arrays
• Believing root shouldn't have children
• Assuming console.log syntax is wrong

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

hard

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

B. Use an array because it allows fast access to any employee by index.

C. Use a linked list because it is simple and efficient for sequential access.

D. Use a stack because it stores employees in last-in-first-out order.

Solution

1. Step 1: Analyze the problem requirements

   The organizational chart has a hierarchy where each employee can have many subordinates, forming a tree-like structure.

2. Step 2: Compare data structures

   Arrays and linked lists are linear and cannot represent multiple children per node naturally. Trees allow each node to have multiple children, matching the hierarchy.

3. Final Answer:

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

4. Quick Check:

   Hierarchy with multiple children = tree = C [OK]

Hint: Hierarchy with multiple children needs trees, not linear lists [OK]

Common Mistakes:

• Choosing arrays for hierarchical data
• Using linked lists for multi-child nodes
• Confusing stack usage with hierarchy