Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - 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 & hierarchical data

↓

Use Tree Structure

↓

Store data in nodes with children

↓

Efficient search, insert, hierarchical representation

Shows why arrays and linked lists fall short for some tasks and how trees solve those problems by organizing data hierarchically.

Execution Sample

DSA C++

Array: fixed size, linear search
Linked List: dynamic size, linear search
Tree: nodes with children, fast search

Compares how arrays, linked lists, and trees store and access data differently.

Execution Table

Step	Operation	Data Structure	Limitations	Visual State
1	Create array with 5 elements	Array	Fixed size, cannot grow	[10, 20, 30, 40, 50]
2	Search for 30 in array	Array	Linear search, O(n)	[10, 20, 30, 40, 50]
3	Create linked list with 3 nodes	Linked List	Dynamic size, but linear search	10 -> 20 -> 30 -> null
4	Search for 30 in linked list	Linked List	Linear search, O(n)	10 -> 20 -> 30 -> null
5	Create tree with root 20, children 10 and 30	Tree	Hierarchical, allows fast search	20 / \ 10 30
6	Search for 30 in tree	Tree	Fast search, O(log n) if balanced	20 / \ 10 30
7	Insert 25 in tree	Tree	Maintains order, fast insert	20 / \ 10 30 / 25
8	End	-	-	-

💡 Trees provide hierarchical structure and faster search compared to arrays and linked lists.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7
Array	empty	[10,20,30,40,50]	[10,20,30,40,50]	[10,20,30,40,50]
LinkedList	empty	10->20->30->null	10->20->30->null	10->20->30->null
Tree	empty	empty	20(root) with 10 and 30 children	20(root) with 10, 30 children; 30 has 25 child

Key Moments - 3 Insights

Why can't arrays grow dynamically like linked lists?

Arrays have fixed size allocated in memory (see Step 1), so they cannot grow without creating a new array. Linked lists can add nodes dynamically (Step 3).

Why is searching slow in arrays and linked lists?

Both arrays and linked lists require checking elements one by one (Steps 2 and 4), leading to linear time search. Trees organize data hierarchically (Step 6) for faster search.

How do trees allow faster search than linked lists?

Trees split data into branches (Step 5), so search can skip large parts of data, unlike linked lists which check each node sequentially.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state of the tree after Step 7?

A [10, 20, 30, 40, 50]

B 20(root) with 10 and 30 children; 30 has 25 child

C 10 -> 20 -> 30 -> null

D 20(root) with 10 and 30 children only

💡 Hint

Check the Visual State column at Step 7 in the execution table.

At which step does the linked list get created?

A Step 2

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the Operation column for linked list creation.

If arrays could grow dynamically, which limitation would be removed?

A Fixed size limitation

B Linear search time

C Hierarchical data storage

D Dynamic insertion in middle

💡 Hint

Refer to the Limitations column for arrays in Step 1.

Concept Snapshot

Arrays: fixed size, fast access by index, slow search
Linked Lists: dynamic size, slow search, sequential access
Trees: hierarchical nodes, fast search and insert, represent relationships
Trees solve fixed size and slow search problems of arrays and linked lists

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 because they check elements one by one. Linked lists can grow but still search slowly by checking nodes one by one. Trees organize data in a hierarchy with nodes and children, allowing faster search and insertion. The execution table shows arrays, linked lists, and trees with their states and limitations. Trees provide a structure that supports efficient data operations that arrays and linked lists cannot do well.

Practice

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

easy

A. Because trees always provide faster access than arrays and linked lists

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 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 order, 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 family trees or file systems.

3. Final Answer:

   Trees represent hierarchical relationships which arrays and linked lists cannot -> Option D

4. Quick Check:

   Hierarchical data needs trees = Because trees can represent hierarchical relationships which arrays and linked lists cannot [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node* left; Node right; };

D. struct Node { int data; Node left; Node* right; };

Solution

1. Step 1: Understand pointer usage in tree nodes

   Each child node should be a pointer to allow dynamic linking and avoid infinite size.

2. Step 2: Check each option for correct pointer usage

   struct Node { int data; Node* left; Node* right; }; uses pointers for both left and right child nodes, which is correct. Options A, B, and C mix pointers and objects incorrectly.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes must be pointers = struct Node { int data; Node* left; Node* right; }; [OK]

Hint: Child nodes are pointers to avoid infinite size [OK]

Common Mistakes:

• Declaring child nodes as objects causing infinite recursion
• Mixing pointers and objects incorrectly
• Forgetting to use pointers for children

3. Consider this C++ code snippet for a binary tree node and insertion:

struct Node {
  int data;
  Node* left;
  Node* right;
  Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->left->left = new Node(3);

std::cout << root->left->left->data << std::endl;

What will be the output?

medium

A. 5

B. 3

C. 10

D. 15

Solution

1. Step 1: Trace the tree construction

   Root node has value 10. Left child is 5, right child is 15. Left child's left child is 3.

2. Step 2: Identify the printed value

   The code prints root->left->left->data, which is the left child of 5, value 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   root->left->left = 3 [OK]

Hint: Follow pointers step-by-step to find value [OK]

Common Mistakes:

• Confusing left and right children
• Printing root->left->data instead of left->left
• Assuming default values instead of assigned

4. The following code tries to create a binary tree node but causes a compilation error. What is the error?

struct Node {
  int data;
  Node left;
  Node right;
  Node(int val) : data(val) {}
};

int main() {
  Node root(10);
  return 0;
}

medium

A. Error due to missing initialization of left and right nodes

B. Error because constructor syntax is wrong

C. Error because Node contains objects of its own type causing infinite size

D. No error, code compiles fine

Solution

1. Step 1: Analyze struct member types

   Node contains members left and right of type Node (not pointers), causing recursive embedding.

2. Step 2: Understand compilation error cause

   This recursive embedding causes infinite size, which is not allowed by the compiler.

3. Final Answer:

   Error because Node contains objects of its own type causing infinite size -> Option C

4. Quick Check:

   Struct with own type members causes infinite size error [OK]

Hint: Use pointers for self-referential structs to avoid infinite size [OK]

Common Mistakes:

• Thinking constructor syntax is wrong
• Assuming missing initialization causes error
• Believing code compiles fine

5. You want to represent a company's organizational chart where each manager can have multiple direct reports. Why is a tree a better choice than arrays or linked lists for this structure?

hard

A. Because trees allow multiple children per node, representing multiple reports naturally

B. Because arrays can only store numbers, not objects

C. Because linked lists cannot store hierarchical data at all

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

Solution

1. Step 1: Understand the organizational chart structure

   Each manager can have multiple direct reports, which is a hierarchical relationship with branching.

2. Step 2: Compare data structures for representing hierarchy

   Arrays and linked lists are linear and cannot naturally represent multiple children per node, but trees can.

3. Final Answer:

   Trees allow multiple children per node, representing multiple reports naturally -> Option A

4. Quick Check:

   Multiple children per node = trees [OK]

Hint: Multiple children per node? Use trees [OK]

Common Mistakes:

• Thinking arrays cannot store objects
• Believing linked lists cannot store any hierarchy
• Assuming trees always use less memory