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

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

Start: Need to store data

↓

Try Array

→Fast access by index

↓

Try Linked List

→Easy insert/delete

↓

Limitations

↓

Arrays: Fixed size, slow insert/delete

↓

Linked Lists: Slow search, no hierarchy

↓

Need structure for hierarchy & fast search

↓

Use Tree: Nodes with children, fast search & hierarchy

Shows why arrays and linked lists are limited and how trees solve hierarchical data and fast search needs.

Execution Sample

DSA Javascript

const array = [10, 20, 30];
const linkedList = { val: 10, next: { val: 20, next: null } };
// Tree node example
const tree = { val: 10, children: [{ val: 20, children: [] }, { val: 30, children: [] }] };

Shows simple array, linked list, and tree structures to compare their shapes and capabilities.

Execution Table

Step	Operation	Data Structure	Limitation Found	Visual State
1	Create array with 3 elements	Array	Fixed size, slow insert/delete in middle	[10, 20, 30]
2	Create linked list with 2 nodes	Linked List	Slow search, no hierarchy	10 -> 20 -> null
3	Try to represent hierarchy with array or linked list	Array / Linked List	Cannot represent parent-child easily	Array: flat [10, 20, 30] Linked List: linear 10 -> 20 -> null
4	Create tree with root and children	Tree	None (solves hierarchy and search)	10 ├─ 20 └─ 30
5	Search for value 30 in tree	Tree	Fast search by traversing children	Visited nodes: 10 -> 20 -> 30
6	Try to insert new child 40 under 20	Tree	Easy insert under parent node	10 ├─ 20 │ └─ 40 └─ 30
7	Try to insert new element in middle of array	Array	Slow, need shift elements	[10, 20, 30] -> Insert 25 at index 2 -> [10, 20, 25, 30]
8	Try to insert new node in middle of linked list	Linked List	Need to traverse to position, then insert	10 -> 20 -> null -> Insert 15 after 10 -> 10 -> 15 -> 20 -> null
9	Conclusion: Trees allow hierarchy and efficient search/insert	Tree	Best for hierarchical data	10 ├─ 20 │ └─ 40 └─ 30
10	End	-	-	-

💡 End of demonstration showing why trees are needed beyond arrays and linked lists.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 6	After Step 9
array	[]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]
linkedList	null	null	10 -> 20 -> null	10 -> 20 -> null	10 -> 20 -> null	10 -> 20 -> null
tree	null	null	null	10 ├─ 20 └─ 30	10 ├─ 20 │ └─ 40 └─ 30	10 ├─ 20 │ └─ 40 └─ 30

Key Moments - 3 Insights

Why can't arrays represent hierarchical data well?

Arrays store data in a flat sequence without parent-child links, so they cannot show hierarchy like trees do (see execution_table step 3).

Why is inserting in the middle of an array slow?

Because arrays need to shift all elements after the insertion point, which takes time (see execution_table step 7).

How do trees allow fast search compared to linked lists?

Trees organize data in branches, so you can skip large parts of data by choosing child nodes, unlike linked lists which require checking each node one by one (see execution_table step 5).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the tree?

A 10 -> 20 -> 30 -> null

B 10 ├─ 20 └─ 30

C [10, 20, 30]

D 10 └─ 20 └─ 30

💡 Hint

Check the Visual State column at step 4 in execution_table.

At which step does the linked list first appear with nodes?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the Data Structure and Visual State columns for linked list creation.

If we want to insert a new child under node 20, which data structure allows easy insertion?

A Tree

B Linked List

C Array

D None

💡 Hint

See execution_table step 6 for insertion under node 20.

Concept Snapshot

Why Trees Exist and What Linked Lists and Arrays Cannot Do

- Arrays: fast index access but fixed size and slow middle insert/delete
- Linked Lists: easy insert/delete but slow search and no hierarchy
- Trees: hierarchical nodes with children, fast search and flexible insert
- Trees solve limitations of arrays and linked lists for hierarchical data
- Use trees when data has parent-child relationships or needs fast search

Full Transcript

This lesson shows why arrays and linked lists have limits and why trees exist. Arrays store data in a flat list with fast access by index but are fixed size and slow to insert or delete in the middle. Linked lists allow easy insert and delete but searching is slow and they cannot represent hierarchy. Trees organize data in nodes with children, allowing fast search and representing parent-child relationships. The execution steps show arrays, linked lists, and trees being created and their limitations. Trees allow easy insertion of child nodes and fast searching by traversing branches. This explains why trees are used when data needs hierarchy and efficient search beyond what arrays and linked lists can do.

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