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 for Hierarchical Data

Which of the following best explains why trees are preferred over arrays or linked lists for representing hierarchical data?

A Arrays and linked lists cannot store data in any order.

B Arrays and linked lists use more memory than trees for hierarchical data.

C Trees are easier to implement than arrays and linked lists.

D Trees allow efficient parent-child relationships and multiple branches, which arrays and linked lists cannot represent naturally.

💡 Hint

Think about how data with multiple levels and branches is organized.

Trees naturally represent hierarchical data with nodes having multiple children, unlike arrays or linked lists which are linear structures.

❓ Predict Output

intermediate

Output of Traversing a Simple Tree Structure

Given the following tree node structure and traversal code, what is the output?

DSA C

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

void preorder(struct Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    struct Node n1 = {1, NULL, NULL};
    struct Node n2 = {2, NULL, NULL};
    struct Node n3 = {3, &n1, &n2};
    preorder(&n3);
    return 0;
}

A 3 1 2

B 1 3 2

C 1 2 3

D 3 2 1

💡 Hint

Preorder traversal visits root first, then left subtree, then right subtree.

The preorder traversal prints the root node data first, then recursively visits left and right children.

🔧 Debug

advanced

Identify the Error in Tree Node Insertion Code

What error will the following code cause when inserting a new node into a binary tree?

DSA C

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

void insert(struct Node* root, int value) {
    if (value < root->data) {
        if (root->left == NULL) {
            root->left = malloc(sizeof(struct Node));
            root->left->data = value;
            root->left->left = NULL;
            root->left->right = NULL;
        } else {
            insert(root->left, value);
        }
    } else {
        if (root->right == NULL) {
            root->right = malloc(sizeof(struct Node));
            root->right->data = value;
            root->right->left = NULL;
            root->right->right = NULL;
        } else {
            insert(root->right, value);
        }
    }
}

A Segmentation fault due to dereferencing NULL pointer when assigning data.

B Compilation error because of missing return statement.

C Infinite recursion causing stack overflow.

D No error; code inserts node correctly.

💡 Hint

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

The code tries to assign data to root->left->data without allocating memory for root->left, causing a crash.

❓ Predict Output

advanced

Result of Searching a Value in a Binary Search Tree

What is the output of the following code when searching for value 5?

DSA C

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

int search(struct Node* root, int value) {
    if (root == NULL) return 0;
    if (root->data == value) return 1;
    if (value < root->data) return search(root->left, value);
    else return search(root->right, value);
}

int main() {
    struct Node n1 = {3, NULL, NULL};
    struct Node n2 = {7, NULL, NULL};
    struct Node n3 = {5, &n1, &n2};
    int found = search(&n3, 5);
    printf("%d", found);
    return 0;
}

A 3

B 0

C 1

D Compilation error

💡 Hint

Search returns 1 if value is found, 0 otherwise.

The value 5 is at the root node, so search returns 1 and prints it.

🧠 Conceptual

expert

Why Linked Lists and Arrays Cannot Efficiently Represent Multi-Branch Hierarchies

Which statement best explains why linked lists and arrays are inefficient for representing multi-branch hierarchical data compared to trees?

A Linked lists and arrays use more memory than trees for the same data.

B Linked lists and arrays are linear structures and cannot naturally represent nodes with multiple children without complex indexing or multiple lists.

C Trees are always faster to traverse than linked lists and arrays.

D Linked lists and arrays cannot store data of different types.

💡 Hint

Consider how many children a node can have and how that fits into linear vs hierarchical structures.

Linked lists and arrays are linear and do not support multiple branches per node easily, requiring complex workarounds, while trees naturally support multi-branch nodes.

Practice

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

easy

A. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide.

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 always have faster access time than arrays and linked lists.

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data linearly, which makes representing hierarchical relationships difficult and inefficient.

2. Step 2: Identify the advantage of trees

   Trees naturally represent hierarchical data with parent-child relationships, allowing efficient searching and organization of such data.

3. Final Answer:

   Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide. -> Option A

4. Quick Check:

   Hierarchical data needs trees = A [OK]

Hint: Trees handle 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 time

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

easy

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

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

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

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

Solution

1. Step 1: Check struct declaration syntax in C

   In C, to declare a struct with pointers to itself, use 'struct Node*' for left and right child pointers.

2. Step 2: Validate typedef usage

   typedef struct Node { int data; struct Node* left; struct Node* right; } Node; correctly defines the struct and typedefs it as Node for easy use.

3. Final Answer:

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

4. Quick Check:

   Correct self-referential struct syntax = B [OK]

Hint: Use 'struct Node*' for child pointers in C structs [OK]

Common Mistakes:

• Using 'Node*' inside struct before typedef
• Declaring child nodes as struct instead of pointers
• Incorrect typedef syntax

3. Consider the following C code that creates a simple binary tree node and prints its data:

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int main() {
  Node root = {10, NULL, NULL};
  printf("%d", root.data);
  return 0;
}

What is the output of this program?

medium

A. Compilation error

B. 0

C. Garbage value

D. 10

Solution

1. Step 1: Analyze struct initialization

   The root node is initialized with data = 10 and both children as NULL pointers.

2. Step 2: Check printf output

   Printing root.data will output 10 as it is explicitly set.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Initialized data printed = 10 [OK]

Hint: Initialized struct fields print their values directly [OK]

Common Mistakes:

• Assuming uninitialized fields print garbage
• Confusing pointer NULL with data value
• Expecting compilation error due to struct

4. The following C code attempts to create a binary tree node but has an error:

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int main() {
  Node* root;
  root->data = 5;
  root->left = NULL;
  root->right = NULL;
  return 0;
}

What is the error and how to fix it?

medium

A. root is uninitialized pointer; fix by allocating memory with malloc.

B. root should be a struct, not a pointer; fix by declaring 'Node root;' instead.

C. Missing semicolon after struct definition; add semicolon.

D. Cannot assign NULL to pointers; use 0 instead.

Solution

1. Step 1: Identify pointer initialization issue

   root is declared as a pointer but not assigned memory, so accessing root->data causes undefined behavior.

2. Step 2: Fix by allocating memory

   Use malloc to allocate memory before accessing members: root = malloc(sizeof(Node));

3. Final Answer:

   root is uninitialized pointer; fix by allocating memory with malloc. -> Option A

4. Quick Check:

   Pointer must point to allocated memory = C [OK]

Hint: Always malloc before using pointer to struct [OK]

Common Mistakes:

• Using pointer without allocation
• Confusing pointer and struct variable
• Ignoring memory allocation errors

5. You want to represent a company's organizational chart where each manager can have multiple employees reporting to them. Why is a tree a better data structure than arrays or linked lists for this, and how would you implement it in C?

hard

A. Arrays are better because they allow random access; implement with a large array of employees.

B. Trees represent hierarchical relationships naturally; implement using nodes with data and a list of child pointers.

C. Linked lists are better because they are simple; implement with a single linked list of all employees.

D. Trees are not suitable; use hash tables instead for fast lookup.

Solution

1. Step 1: Understand the hierarchical nature of organizational charts

   Each manager can have multiple employees, forming a tree-like structure with parent-child relationships.

2. Step 2: Compare data structures for this use case

   Arrays and linked lists are linear and cannot represent multiple children per node efficiently; trees allow multiple children per node naturally.

3. Step 3: Implementation approach in C

   Use a struct with data and a dynamic array or linked list of pointers to child nodes to represent multiple employees under a manager.

4. Final Answer:

   Trees represent hierarchical relationships naturally; implement using nodes with data and a list of child pointers. -> Option B

5. Quick Check:

   Hierarchy needs trees with child lists = A [OK]

Hint: Use trees with child lists for multi-level hierarchy [OK]

Common Mistakes:

• Trying to use arrays for hierarchical data
• Using single linked list for multi-child nodes
• Ignoring the need for multiple children pointers