Tree vs Array vs Linked List When Hierarchy Matters in DSA Javascript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Traversing a Simple Tree Structure

Consider the following JavaScript code that represents a simple tree using nested objects. What will be the output when we print the names in preorder traversal?

DSA Javascript

const tree = {
  name: 'root',
  children: [
    { name: 'child1', children: [] },
    { name: 'child2', children: [
      { name: 'grandchild1', children: [] }
    ] }
  ]
};

function preorder(node) {
  let result = [];
  result.push(node.name);
  for (const child of node.children) {
    result = result.concat(preorder(child));
  }
  return result;
}

console.log(preorder(tree).join(' -> ') + ' -> null');

A root -> child1 -> child2 -> grandchild1 -> null

B root -> child2 -> grandchild1 -> child1 -> null

C child1 -> root -> child2 -> grandchild1 -> null

D root -> grandchild1 -> child1 -> child2 -> null

💡 Hint

Think about visiting the root first, then each child from left to right.

The preorder traversal visits the root node first, then recursively visits each child in order. So the order is root, child1, child2, then grandchild1.

❓ Predict Output

intermediate

Linked List vs Array for Hierarchical Data

Given a linked list and an array representing the same sequence of nodes, which output correctly shows the linked list traversal?

DSA Javascript

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

const head = new Node('A');
head.next = new Node('B');
head.next.next = new Node('C');

let current = head;
let output = '';
while (current) {
  output += current.value + ' -> ';
  current = current.next;
}
output += 'null';
console.log(output);

A A -> B -> C -> null

B A, B, C

C [A, B, C]

D null -> C -> B -> A

💡 Hint

Linked list traversal prints nodes followed by arrows ending with null.

The linked list traversal prints each node's value followed by '->' and ends with 'null'. Arrays print differently.

🧠 Conceptual

advanced

Why Use Trees Over Arrays for Hierarchical Data?

Which of the following is the best reason to use a tree data structure instead of a simple array when representing hierarchical data?

A Arrays use less memory than trees for hierarchical data.

B Arrays can only store numbers, trees can store any data.

C Trees are always faster to traverse than arrays.

D Trees allow representing parent-child relationships naturally, while arrays do not.

💡 Hint

Think about how hierarchy and relationships are stored.

Trees naturally represent parent-child relationships, which arrays cannot do directly. Arrays are linear and do not capture hierarchy.

🔧 Debug

advanced

Identify the Error in Linked List Insertion Code

What error will the following code produce when trying to insert a new node at the end of a linked list?

DSA Javascript

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

function insertAtEnd(head, value) {
  let newNode = new Node(value);
  let current = head;
  while (current.next) {
    current = current.next;
  }
  current.next = newNode;
  return head;
}

let head = null;
head = insertAtEnd(head, 'A');

A ReferenceError: head is not defined

B No error, linked list updated correctly

C TypeError: Cannot read property 'next' of null

D SyntaxError: Unexpected token"

💡 Hint

Check what happens when head is null at the start.

The code assumes head is not null and tries to access current.next, but current is null initially, causing a TypeError.

🚀 Application

expert

Choosing Data Structure for File System Hierarchy

You need to design a data structure to represent a file system hierarchy where folders can contain files and other folders. Which data structure is the best choice and why?

A Linked List, because it is simple and uses less memory than trees.

B Tree, because it naturally models nested folders and files with parent-child relationships.

C Hash Map, because it stores key-value pairs for file names and contents.

D Array, because it allows fast random access to files and folders.

💡 Hint

Think about how folders contain other folders and files inside them.

A tree structure is best for file systems because it models the nested hierarchy of folders and files with parent-child links.

Practice

1. Which data structure is best suited to represent a family tree where each person can have multiple children?

easy

A. Stack

B. Array

C. Linked List

D. Tree

Solution

1. Step 1: Understand the hierarchy requirement

   A family tree has a parent-child relationship with multiple children per parent, which is a hierarchical structure.

2. Step 2: Match data structure to hierarchy

   Trees naturally represent hierarchical data with nodes and branches, allowing multiple children per node.

3. Final Answer:

   Tree -> Option D

4. Quick Check:

   Hierarchy with multiple children = Tree [OK]

Hint: Hierarchy with multiple children? Use Tree [OK]

Common Mistakes:

• Choosing Array which is linear, not hierarchical
• Choosing Linked List which supports only one next node
• Confusing Stack with hierarchical structure

2. Which of the following is the correct way to declare a linked list node in JavaScript?

easy

A. const node = { value: 5, next: null };

B. const node = [5, null];

C. const node = new Array(5, null);

D. const node = { next: 5, value: null };

Solution

1. Step 1: Understand linked list node structure

   A linked list node typically has a value and a pointer to the next node (next).

2. Step 2: Check each option for correct syntax

   const node = { value: 5, next: null }; correctly uses an object with 'value' and 'next' keys. Others either use arrays or swap keys incorrectly.

3. Final Answer:

   const node = { value: 5, next: null }; -> Option A

4. Quick Check:

   Linked list node = object with value and next [OK]

Hint: Linked list node = object with value and next [OK]

Common Mistakes:

• Using arrays instead of objects for nodes
• Swapping value and next keys
• Using Array constructor incorrectly

3. What will be the output of the following JavaScript code that builds a simple tree structure?

const tree = {
  value: 'root',
  children: [
    { value: 'child1', children: [] },
    { value: 'child2', children: [
      { value: 'grandchild1', children: [] }
    ] }
  ]
};

console.log(tree.children[1].children[0].value);

medium

A. "grandchild1"

B. "child2"

C. "child1"

D. undefined

Solution

1. Step 1: Trace the tree object structure

   The root has two children: 'child1' and 'child2'. 'child2' has one child: 'grandchild1'.

2. Step 2: Access the nested value

   tree.children[1] is 'child2', its children[0] is 'grandchild1', so accessing value gives 'grandchild1'.

3. Final Answer:

   "grandchild1" -> Option A

4. Quick Check:

   tree.children[1].children[0].value = "grandchild1" [OK]

Hint: Follow children indices step-by-step [OK]

Common Mistakes:

• Confusing child indices (0 vs 1)
• Assuming children is a single node, not array
• Accessing wrong property name

4. The following code attempts to create a linked list but has an error. What is the error?

const node1 = { value: 1, next: null };
const node2 = { value: 2, next: null };
node1.next = node2;
node2.next = node1;
console.log(node1.next.next.value);

medium

A. node2.next should be null, not node1

B. node1.next is null, so accessing next.next causes error

C. It creates an infinite loop by linking nodes circularly

D. Syntax error in object declaration

Solution

1. Step 1: Analyze the linked list connections

   node1.next points to node2, and node2.next points back to node1, creating a circular link.

2. Step 2: Understand the effect of circular links

   Accessing node1.next.next.value goes from node1 to node2, then back to node1, causing infinite traversal if looped.

3. Final Answer:

   It creates an infinite loop by linking nodes circularly -> Option C

4. Quick Check:

   Circular links cause infinite loops [OK]

Hint: Check if next points back to previous node [OK]

Common Mistakes:

• Ignoring circular reference causing infinite loop
• Assuming next.next is null
• Thinking it's a syntax error

5. You have a nested array representing a company's hierarchy like this:

const company = [
  { name: 'CEO', reports: [
    { name: 'Manager1', reports: [] },
    { name: 'Manager2', reports: [
      { name: 'Employee1', reports: [] }
    ] }
  ] }
];

Which data structure would be best to convert this into for efficient traversal and why?

hard

A. Convert to a Linked List because it allows easy sequential access to employees.

B. Convert to a Tree because it naturally represents hierarchical relationships with multiple children.

C. Convert to a flat Array because arrays are faster to traverse than trees.

D. Convert to a Stack because it helps in depth-first traversal.

Solution

1. Step 1: Understand the nested array structure

   The company hierarchy has multiple levels with managers and employees reporting to them, forming a hierarchy.

2. Step 2: Choose data structure matching hierarchy and traversal needs

   Trees represent hierarchical data with nodes and children, making traversal and queries efficient and natural.

3. Final Answer:

   Convert to a Tree because it naturally represents hierarchical relationships with multiple children. -> Option B

4. Quick Check:

   Hierarchical data = Tree for efficient traversal [OK]

Hint: Hierarchy with multiple levels? Use Tree [OK]

Common Mistakes:

• Choosing Linked List which is linear, not hierarchical
• Choosing flat Array losing hierarchy info
• Confusing Stack with data structure for storage