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.