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.