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].