Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Typescript - Why It Works

Concept Flow - Why Trees Exist and What Linked Lists and Arrays Cannot Do

Start: Need to store data

↓

Try Array

→Fixed size, slow search

↓

Try Linked List

→Dynamic size, slow search

↓

Need fast search & hierarchy

↓

Use Tree Structure

↓

Store data in nodes with children

↓

Fast search, hierarchical data, flexible size

Shows why arrays and linked lists fall short for some tasks and how trees solve these by organizing data hierarchically for fast search and flexible structure.

Execution Sample

DSA Typescript

Array: [10, 20, 30, 40]
LinkedList: 10 -> 20 -> 30 -> 40 -> null
Tree:
    20
   /  \
 10    30
          \
           40

Shows data stored in array, linked list, and tree forms to compare structure and access.

Execution Table

Step	Operation	Data Structure	Limitations / Advantages	Visual State
1	Store 4 elements in Array	Array	Fixed size, slow search if unsorted	[10, 20, 30, 40]
2	Store 4 elements in Linked List	Linked List	Dynamic size, slow search (linear)	10 -> 20 -> 30 -> 40 -> null
3	Store 4 elements in Tree	Tree	Hierarchical, fast search (log n), flexible	20 / \ 10 30 \ 40
4	Search for 30 in Array	Array	Must check each element	Search linear: 10, 20, 30 (found)
5	Search for 30 in Linked List	Linked List	Must traverse nodes one by one	Traverse: 10 -> 20 -> 30 (found)
6	Search for 30 in Tree	Tree	Compare and go left/right, faster	At 20: go right -> 30 (found)
7	Add 25 to Array	Array	Fixed size, need resize	Resize needed to add element
8	Add 25 to Linked List	Linked List	Add at end easily	10 -> 20 -> 30 -> 40 -> 25 -> null
9	Add 25 to Tree	Tree	Add maintaining order	20 / \ 10 30 / \ 25 40
10	Conclusion	Tree	Trees handle hierarchy and fast search better than arrays or lists	Hierarchical structure with fast access

💡 Trees provide hierarchical structure and faster search, overcoming array and linked list limitations.

Variable Tracker

Data Structure	Initial State	After Adding Elements	After Search	Final State
Array	[]	[10, 20, 30, 40]	Search linear through elements	[10, 20, 30, 40]
Linked List	null	10 -> 20 -> 30 -> 40 -> null	Traverse nodes one by one	10 -> 20 -> 30 -> 40 -> 25 -> null
Tree	empty	20 / \ 10 30 \ 40	Compare nodes left/right	20 / \ 10 30 / \ 25 40

Key Moments - 3 Insights

Why can't arrays handle dynamic size easily?

Arrays have fixed size; adding elements beyond capacity requires creating a new larger array and copying elements, as shown in execution_table step 7.

Why is searching slow in linked lists compared to trees?

Linked lists require checking each node one by one (step 5), while trees use comparisons to skip large parts of data (step 6), making search faster.

How do trees organize data differently from arrays and linked lists?

Trees store data in nodes with children forming a hierarchy (step 3 and 9), allowing faster search and representing relationships, unlike linear arrays or lists.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, how does the tree find 30 faster than the linked list?

A By comparing and moving left or right child nodes

B By checking every element one by one

C By resizing the data structure

D By storing elements in a fixed order

💡 Hint

See step 6 in execution_table where tree compares and goes right to find 30 quickly.

At which step does the array need resizing to add a new element?

A Step 3

B Step 9

C Step 7

D Step 5

💡 Hint

Check step 7 in execution_table where adding 25 to array requires resize.

According to variable_tracker, which data structure shows a change from empty to hierarchical nodes?

A Array

B Tree

C Linked List

D None

💡 Hint

Look at variable_tracker row for Tree showing empty to hierarchical structure.

Concept Snapshot

Why Trees Exist and What Linked Lists and Arrays Cannot Do

- Arrays: fixed size, slow search if unsorted
- Linked Lists: dynamic size, slow linear search
- Trees: hierarchical nodes, fast search (log n), flexible size
- Trees solve problems of slow search and lack of hierarchy
- Use trees for data with relationships and fast lookup

Full Transcript

This lesson shows why arrays and linked lists are not enough for some data storage needs. Arrays have fixed size and slow search if unsorted. Linked lists can grow but still search slowly by checking nodes one by one. Trees organize data in nodes with children, forming a hierarchy. This lets trees search faster by comparing and moving left or right, skipping many elements. Trees also handle dynamic size and represent relationships naturally. The execution steps show storing, searching, and adding elements in arrays, linked lists, and trees, highlighting their differences and advantages. Trees exist to overcome the limitations of arrays and linked lists, especially for fast search and hierarchical data.

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