Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why use trees instead of arrays or linked lists?

Which of the following is a key reason trees are used instead of arrays or linked lists?

A Trees do not require pointers or references to connect elements.

B Trees use less memory than arrays and linked lists for storing the same data.

C Trees always store data in a linear order like arrays and linked lists.

D Trees allow faster searching in sorted data compared to arrays and linked lists.

💡 Hint

Think about how quickly you can find an item in a sorted list versus a tree.

Trees, especially binary search trees, allow searching in O(log n) time by dividing data into branches, which is faster than linear search in linked lists or arrays.

❓ Predict Output

intermediate

Output of tree traversal vs array traversal

What is the output of the following JavaScript code that traverses a simple binary tree and an array?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);

function inorder(node) {
  if (!node) return [];
  return [...inorder(node.left), node.value, ...inorder(node.right)];
}

const arr = [1, 2, 3];

console.log(inorder(root));
console.log(arr);

A

[2, 1, 3]
[1, 2, 3]

B

[1, 2, 3]
[1, 2, 3]

C

[2, 3, 1]
[3, 2, 1]

D

[3, 1, 2]
[1, 2, 3]

💡 Hint

Inorder traversal visits left child, then node, then right child.

The inorder traversal of the tree visits nodes in the order 2, 1, 3. The array remains in its original order.

🔧 Debug

advanced

Why does this linked list fail to represent hierarchical data?

Consider this linked list code trying to represent a family tree. Why does it fail to represent the hierarchy properly?

DSA Javascript

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

const head = new ListNode('Grandparent');
head.next = new ListNode('Parent');
head.next.next = new ListNode('Child');

// Trying to represent family tree with linked list

A The code has a syntax error in the constructor.

B Linked lists can only represent linear sequences, not branching hierarchies.

C Linked lists require a 'parent' pointer to represent hierarchies.

D The linked list nodes must have 'left' and 'right' properties to work.

💡 Hint

Think about how family trees branch out compared to a single line.

Linked lists connect nodes in a single line, so they cannot represent branching structures like trees.

❓ Predict Output

advanced

Output of searching in array vs tree

What is the output of the following JavaScript code that searches for the number 5 in an array and a binary search tree?

DSA Javascript

const arr = [1, 3, 5, 7, 9];

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

const root = new TreeNode(7);
root.left = new TreeNode(3);
root.right = new TreeNode(9);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(5);

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

function searchTree(node, target) {
  if (!node) return false;
  if (node.value === target) return true;
  if (target < node.value) return searchTree(node.left, target);
  else return searchTree(node.right, target);
}

console.log(searchArray(arr, 5));
console.log(searchTree(root, 5));

A

true
true

B

false
true

C

true
false

D

false
false

💡 Hint

Both array and tree contain the number 5.

The number 5 is found in both the array and the tree, so both searches return true.

🧠 Conceptual

expert

Why are trees better for representing hierarchical data?

Which statement best explains why trees are preferred over arrays and linked lists for hierarchical data?

A Trees use less memory than arrays and linked lists for the same data.

B Arrays and linked lists can only store numbers, not objects or nodes.

C Trees allow multiple child nodes per parent, enabling natural representation of hierarchies.

D Arrays and linked lists cannot be traversed or searched.

💡 Hint

Think about how family trees or company structures branch out.

Trees allow each node to have multiple children, which matches the branching nature of hierarchical data, unlike arrays or linked lists which are linear.

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