Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - Quick Recap

Recall & Review

beginner

Why do we need trees when we already have arrays and linked lists?

Trees help organize data in a way that allows fast searching, insertion, and deletion in hierarchical relationships, which arrays and linked lists cannot do efficiently.

beginner

What is a key limitation of arrays compared to trees?

Arrays have fixed size and slow insertion/deletion in the middle, while trees can grow dynamically and allow faster updates in hierarchical data.

beginner

Why can't linked lists efficiently represent hierarchical data?

Linked lists are linear and only connect elements in a sequence, so they cannot naturally represent parent-child relationships like trees do.

intermediate

How do trees improve search operations compared to arrays and linked lists?

Trees like binary search trees allow searching in O(log n) time by dividing data into branches, while arrays and linked lists require O(n) time for search.

beginner

What real-life example helps explain why trees are useful?

A family tree shows relationships between people in generations, which arrays or linked lists cannot represent well because they are linear, not hierarchical.

Which data structure is best for representing hierarchical data?

A Tree

B Array

C Linked List

D Stack

Trees naturally represent hierarchical relationships with parent and child nodes.

What is a main disadvantage of arrays compared to trees?

A Too complex to use

B Cannot store data

C No order of elements

D Fixed size and slow insertion in the middle

Arrays have fixed size and inserting in the middle requires shifting elements, which is slow.

Why can't linked lists efficiently represent parent-child relationships?

A They are too large

B They only connect elements linearly

C They use too much memory

D They are unordered

Linked lists connect elements one after another, so they can't show hierarchical links.

Which operation is faster in trees than in arrays or linked lists?

A Iterating all elements

B Accessing the first element

C Searching for an element

D Appending at the end

Trees can search in O(log n) time by branching, while arrays and linked lists take O(n).

What real-world structure is similar to a tree data structure?

A Family tree

B Queue line

C Array of numbers

D Linked list of songs

A family tree shows hierarchical relationships like a tree data structure.

Explain why trees are needed when arrays and linked lists exist. Include examples of what trees can do better.

Think about how data is connected in real life, not just in a line.

Describe the limitations of arrays and linked lists that trees solve.

Focus on structure and operation speed.

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