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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tree Node Insertion Order

Given the following TypeScript code that inserts nodes into a binary tree, what will be the printed output representing the tree structure in preorder traversal?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) { this.val = val; }
}

function insert(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function preorder(root: TreeNode | null): string {
  if (!root) return '';
  return root.val + ' ' + preorder(root.left) + preorder(root.right);
}

let root: TreeNode | null = null;
[10, 5, 15, 3, 7, 12, 18].forEach(v => {
  root = insert(root, v);
});
console.log(preorder(root).trim());

A 10 5 7 3 15 18 12

B 10 15 18 12 5 7 3

C 3 5 7 10 12 15 18

D 10 5 3 7 15 12 18

💡 Hint

Think about how binary search tree insertion works and how preorder traversal visits nodes.

The insertion builds a binary search tree. Preorder traversal visits root, then left subtree, then right subtree. So the output is the root value first, then recursively the left subtree values, then right subtree values.

🧠 Conceptual

intermediate

Why Trees Are Better Than Arrays for Hierarchical Data

Which of the following best explains why trees are used to represent hierarchical data instead of arrays or linked lists?

A Trees allow multiple branches from a single node, representing parent-child relationships naturally, unlike arrays or linked lists which are linear.

B Arrays and linked lists use more memory than trees for the same data.

C Trees are always faster to search than arrays or linked lists regardless of data structure.

D Arrays and linked lists cannot store numbers, only trees can.

💡 Hint

Think about how data is connected in a family tree or file system.

Trees naturally represent hierarchical relationships with nodes having multiple children. Arrays and linked lists are linear and cannot represent branching structures easily.

🔧 Debug

advanced

Identify the Error in Tree Traversal Code

What error will this TypeScript code produce when trying to perform inorder traversal on a tree?

DSA Typescript

class Node {
  val: number;
  left: Node | null = null;
  right: Node | null = null;
  constructor(val: number) { this.val = val; }
}

function inorder(root: Node | null): number[] {
  let result: number[] = [];
  if (root === null) return result;
  inorder(root.left);
  inorder(root.right);
  return result;
}

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

A [2, 1, 3]

B [] (empty array)

C TypeError: Cannot read property 'left' of undefined

D [1, 2, 3]

💡 Hint

Check how the recursive calls handle the result array.

The recursive calls to inorder do not accumulate results because the result array is local to each call and the recursive calls' results are ignored. So the returned array is empty.

🚀 Application

advanced

Choosing Data Structure for Fast Lookup in Hierarchical Data

You need to store a company's organizational chart where each employee can have multiple subordinates. You want to quickly find all subordinates of any employee. Which data structure is best suited?

A A binary tree because it keeps data sorted and allows fast search.

B A linked list because it is simple and easy to traverse.

C A tree where each node has a list of children, representing multiple subordinates.

D An array because it allows direct index access.

💡 Hint

Think about how to represent multiple children per node efficiently.

A tree with nodes having lists of children naturally models multiple subordinates per employee and allows traversal to find all subordinates efficiently.

❓ Predict Output

expert

Output of Complex Tree Structure After Insertions

What is the output of the following TypeScript code that builds a tree and prints its level order traversal?

DSA Typescript

class TreeNode {
  val: number;
  children: TreeNode[] = [];
  constructor(val: number) { this.val = val; }
}

function levelOrder(root: TreeNode | null): number[] {
  if (!root) return [];
  const queue: TreeNode[] = [root];
  const result: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);
    for (const child of node.children) {
      queue.push(child);
    }
  }
  return result;
}

const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const child3 = new TreeNode(4);
root.children.push(child1, child2);
child1.children.push(child3);
console.log(levelOrder(root));

A [1, 2, 3, 4]

B [1, 3, 2, 4]

C [1, 2, 4, 3]

D [1, 4, 2, 3]

💡 Hint

Level order traversal visits nodes level by level from left to right.

The root is 1, its children 2 and 3 are next, then 2's child 4 is last. So the order is [1, 2, 3, 4].

Practice

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

easy

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

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

C. Because trees always have faster access times than arrays and linked lists.

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

Solution

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

   Arrays and linked lists store data in a linear sequence, which makes it hard to represent hierarchical or branching relationships.

2. Step 2: Identify the unique feature of trees

   Trees allow each element 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 D

4. Quick Check:

   Hierarchical data needs trees = C [OK]

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

Common Mistakes:

• Thinking trees always use less memory
• Believing trees are simpler to implement
• Assuming trees always have faster access

2. Which of the following is the correctly way to declare a simple tree node in TypeScript?

easy

A. class TreeNode { value: number; children: TreeNode[]; constructor(value: number) { this.value = value; this.children = []; } }

B. class TreeNode { value: number; next: TreeNode; constructor(value: number) { this.value = value; this.next = null; } }

C. class TreeNode { value: number; prev: TreeNode; constructor(value: number) { this.value = value; this.prev = null; } }

D. class TreeNode { value: number; array: number[]; constructor(value: number) { this.value = value; this.array = []; } }

Solution

1. Step 1: Identify tree node properties

   A tree node stores a value and multiple children nodes, so it needs a children array.

2. Step 2: Match with the correct class declaration

   class TreeNode { value: number; children: TreeNode[]; constructor(value: number) { this.value = value; this.children = []; } } declares a value and children array, suitable for a tree node. Declarations using next or prev are for linked lists. class TreeNode { value: number; array: number[]; constructor(value: number) { this.value = value; this.array = []; } } uses an array of numbers, not nodes.

3. Final Answer:

   correctly declares a tree node with children array -> Option A

4. Quick Check:

   Tree nodes have children array = A [OK]

Hint: Tree nodes have children arrays, not next or prev pointers [OK]

Common Mistakes:

• Confusing tree nodes with linked list nodes
• Using next or prev instead of children array
• Using array of numbers instead of nodes

3. What will be the output of the following TypeScript code?

class TreeNode {
  value: number;
  children: TreeNode[];
  constructor(value: number) {
    this.value = value;
    this.children = [];
  }
}

const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
root.children.push(child1);
root.children.push(child2);
console.log(root.children.length);

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Understand the tree construction

   A root node with value 1 is created. Two child nodes with values 2 and 3 are created and added to root's children array.

2. Step 2: Count the children of root

   Two children are pushed into root.children, so root.children.length is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Two children added = 2 [OK]

Hint: Count how many children are pushed into the children array [OK]

Common Mistakes:

• Assuming children length is 0 by default
• Confusing children with linked list next pointers
• Counting nodes instead of children array length

4. Find the error in this TypeScript code that tries to create a tree node and add children:

class TreeNode {
  value: number;
  children: TreeNode[];
  constructor(value: number) {
    this.value = value;
    this.children = null;
  }
}

const root = new TreeNode(10);
root.children.push(new TreeNode(20));

medium

A. The constructor should not have parameters.

B. children should be initialized as an empty array, not null.

C. The push method does not exist on arrays.

D. TreeNode class should not have a children property.

Solution

1. Step 1: Check children initialization

   children is set to null, so calling push on null causes an error.

2. Step 2: Correct children initialization

   children should be initialized as an empty array [] to allow push method calls.

3. Final Answer:

   children should be initialized as an empty array, not null -> Option B

4. Quick Check:

   push on null causes error = A [OK]

Hint: Initialize children as [] before pushing nodes [OK]

Common Mistakes:

• Setting children to null instead of []
• Trying to push on null causing runtime error
• Ignoring constructor parameters

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

Choose the best answer.

hard

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

B. Use a linked list because it allows easy insertion and deletion of employees.

C. Use a stack because it follows last-in-first-out which suits organizational charts.

D. Use an array because it stores data sequentially and is easy to access.

Solution

1. Step 1: Understand the problem context

   An organizational chart is hierarchical: managers have multiple subordinates, forming branches.

2. Step 2: Match data structure to hierarchy

   Trees allow nodes to have multiple children, perfectly modeling this hierarchy. Arrays and linked lists are linear, stacks are LIFO structures unsuitable here.

3. Final Answer:

   Use a tree because it naturally models hierarchical relationships -> Option A

4. Quick Check:

   Hierarchy needs trees = D [OK]

Hint: Hierarchies need trees, not linear or LIFO structures [OK]

Common Mistakes:

• Choosing arrays or linked lists for hierarchical data
• Confusing stack behavior with organizational needs
• Ignoring multiple children per node requirement