Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA C++ - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why Trees Are Used Instead of Arrays or Linked Lists

Which of the following is a key reason why trees are used instead of arrays or linked lists?

A Trees allow faster searching and hierarchical data representation.

B Trees use less memory than arrays and linked lists.

C Trees store data in a continuous block of memory.

D Trees do not require pointers or references.

💡 Hint

Think about how data is organized and searched in trees compared to arrays or linked lists.

Trees provide a hierarchical structure that allows faster searching (like binary search trees) and can represent parent-child relationships, which arrays and linked lists cannot do efficiently.

❓ Predict Output

intermediate

Output of Tree Traversal vs Linked List Traversal

Given the following C++ code snippets, what is the output of the tree traversal compared to the linked list traversal?

DSA C++

struct Node {
    int val;
    Node* next;
    Node* left;
    Node* right;
};

// Linked list traversal
void printList(Node* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
}

// Inorder tree traversal
void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->val << " ";
    inorder(root->right);
}

int main() {
    // Linked list: 1 -> 2 -> 3
    Node* head = new Node{1, nullptr, nullptr, nullptr};
    head->next = new Node{2, nullptr, nullptr, nullptr};
    head->next->next = new Node{3, nullptr, nullptr, nullptr};

    // Tree:
    //     2
    //    / \
    //   1   3
    Node* root = new Node{2, nullptr, nullptr, nullptr};
    root->left = new Node{1, nullptr, nullptr, nullptr};
    root->right = new Node{3, nullptr, nullptr, nullptr};

    printList(head);
    std::cout << "\n";
    inorder(root);
    return 0;
}

A 1 2 3\n3 2 1

B 1 2 3\n2 1 3

C 1 2 3\n1 2 3

D 2 1 3\n1 2 3

💡 Hint

Recall how inorder traversal visits nodes in a binary search tree.

The linked list prints nodes in order 1 2 3. The inorder traversal of the tree visits left, root, right, so it prints 1 2 3 as well.

🔧 Debug

advanced

Why Does This Tree Code Cause a Runtime Error?

Consider this C++ code snippet that tries to insert nodes into a binary tree. Why does it cause a runtime error?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
};

void insert(Node* root, int value) {
    if (value < root->val) {
        if (root->left == nullptr) {
            root->left = new Node{value, nullptr, nullptr};
        } else {
            insert(root->left, value);
        }
    } else {
        if (root->right == nullptr) {
            root->right = new Node{value, nullptr, nullptr};
        } else {
            insert(root->right, value);
        }
    }
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    insert(root, 5);
    insert(root, 15);
    return 0;
}

A It overwrites the root node value instead of inserting.

B It tries to assign value to a null pointer without allocating memory.

C It causes a syntax error due to missing semicolons.

D It causes infinite recursion because base case is missing.

💡 Hint

Check what happens when root->left or root->right is nullptr before assignment.

The code tries to assign a value to root->left->val or root->right->val without creating a new Node object first, causing a runtime error (segmentation fault).

📝 Syntax

advanced

Which Option Correctly Defines a Tree Node in C++?

Which of the following C++ struct definitions correctly defines a binary tree node with integer values?

A struct Node { int val; Node left*; Node right*; };

B struct Node { int val; Node left; Node right; };

C struct Node { int val; Node* left; Node right; };

D struct Node { int val; Node* left; Node* right; };

💡 Hint

Remember how pointers are declared in C++ structs.

Option D correctly declares left and right as pointers to Node. Other options have invalid pointer syntax or cause infinite recursion.

🚀 Application

expert

Why Can't Linked Lists Efficiently Represent Hierarchical Data?

Which of the following best explains why linked lists are not efficient for representing hierarchical data structures like file systems or organizational charts?

A Linked lists are linear and cannot represent multiple child nodes per parent efficiently.

B Linked lists require more memory than trees for the same data.

C Linked lists do not allow traversal of elements.

D Linked lists cannot store integer values.

💡 Hint

Think about how many children a node can have in a hierarchy and how linked lists store data.

Linked lists are linear structures where each node points to only one next node, making it inefficient to represent nodes with multiple children as in hierarchical data.

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