Tree vs Array vs Linked List When Hierarchy Matters in DSA C++ - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Traversal in a Simple Tree Structure

Consider the following C++ code that builds a simple tree and prints its nodes in preorder traversal. What is the output?

DSA C++

struct Node {
    int val;
    std::vector<Node*> children;
    Node(int v) : val(v) {}
};

void preorder(Node* root) {
    if (!root) return;
    std::cout << root->val << " ";
    for (auto child : root->children) {
        preorder(child);
    }
}

int main() {
    Node* root = new Node(1);
    root->children.push_back(new Node(2));
    root->children.push_back(new Node(3));
    root->children[0]->children.push_back(new Node(4));
    root->children[1]->children.push_back(new Node(5));
    preorder(root);
    return 0;
}

A 1 2 3 4 5

B 1 3 5 2 4

C 1 2 4 3 5

D 1 4 2 5 3

💡 Hint

Preorder traversal visits the root first, then recursively visits each child in order.

The preorder traversal prints the root node first (1), then recursively visits the first child subtree (2 and its child 4), then the second child subtree (3 and its child 5).

🧠 Conceptual

intermediate

Choosing Data Structure for Hierarchical Data

Which data structure is best suited to represent hierarchical data with multiple levels and variable number of children per node?

A Tree

B Linked List

C Stack

D Array

💡 Hint

Think about how to represent parent-child relationships with multiple children.

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

🔧 Debug

advanced

Identify the Bug in Linked List Hierarchy Representation

This C++ code attempts to represent a hierarchy using a linked list where each node points to its first child and next sibling. What error will occur when running this code?

DSA C++

struct Node {
    int val;
    Node* firstChild;
    Node* nextSibling;
    Node(int v) : val(v), firstChild(nullptr), nextSibling(nullptr) {}
};

int main() {
    Node* root = new Node(1);
    root->firstChild = new Node(2);
    root->firstChild->nextSibling = new Node(3);
    root->firstChild->firstChild = new Node(4);
    std::cout << root->firstChild->nextSibling->firstChild->val << std::endl;
    return 0;
}

A Prints 4

B Segmentation fault (null pointer dereference)

C Compilation error due to missing semicolon

D Prints 3

💡 Hint

Check if nextSibling node has a firstChild before accessing it.

The node with value 3 has no firstChild (nullptr). Accessing firstChild->val causes a segmentation fault.

❓ Predict Output

advanced

Output of Array Representing a Binary Tree

Given the array representation of a binary tree where index 0 is the root, left child at 2*i+1, right child at 2*i+2, what is the output of the inorder traversal printed by the code below?

DSA C++

int arr[] = {1, 2, 3, 4, 5, 6, 7};
void inorder(int i, int n) {
    if (i >= n) return;
    inorder(2*i + 1, n);
    std::cout << arr[i] << " ";
    inorder(2*i + 2, n);
}

int main() {
    inorder(0, 7);
    return 0;
}

A 2 4 5 1 3 6 7

B 1 2 3 4 5 6 7

C 7 6 3 5 2 4 1

D 4 2 5 1 6 3 7

💡 Hint

Inorder traversal visits left child, root, then right child recursively.

The inorder traversal of the binary tree represented by the array visits nodes in the order: 4 2 5 1 6 3 7.

🧠 Conceptual

expert

Why Trees Are Preferred Over Arrays for Dynamic Hierarchies

Why are tree data structures generally preferred over arrays when representing dynamic hierarchical data where nodes can be added or removed frequently?

A Trees allow efficient insertion and deletion without shifting elements, unlike arrays.

B Trees require contiguous memory allocation, making them faster.

C Arrays use less memory than trees for dynamic data.

D Arrays can represent multiple parents for a node, trees cannot.

💡 Hint

Consider how insertion and deletion affect memory layout in arrays vs trees.

Arrays require shifting elements for insertions/deletions which is costly; trees use pointers allowing efficient dynamic updates.

Practice

1. Which data structure is best suited to represent hierarchical relationships like a family tree?

easy

A. Stack

B. Tree

C. Linked List

D. Array

Solution

1. Step 1: Understand hierarchy representation

   Hierarchical data means elements have parent-child relationships, like a family tree.

2. Step 2: Match data structure to hierarchy

   Trees naturally represent hierarchy with nodes connected to children, unlike arrays or linked lists which are linear.

3. Final Answer:

   Tree -> Option B

4. Quick Check:

   Hierarchy needs Tree [OK]

Hint: Hierarchy means parent-child links, use Tree [OK]

Common Mistakes:

• Choosing Array because it's simple
• Choosing Linked List thinking it's hierarchical
• Confusing Stack with hierarchy

2. Which of the following is the correct way to declare a simple linked list node in C++?

easy

A. struct Node { int data; Node& next; };

B. struct Node { int data; Node next; };

C. struct Node { int data; Node next*; };

D. struct Node { int data; Node* next; };

Solution

1. Step 1: Check pointer usage in struct

   Linked list nodes must point to next node using a pointer type (Node*).

2. Step 2: Validate syntax correctness

   struct Node { int data; Node* next; }; uses Node* next; which is correct pointer syntax. Others have invalid pointer or reference syntax.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option D

4. Quick Check:

   Pointer to next node uses Node* [OK]

Hint: Use Node* for next pointer in linked list node [OK]

Common Mistakes:

• Using Node next instead of Node* next
• Using reference Node& which is invalid here
• Incorrect pointer syntax like next*

3. What will be the output of the following C++ code snippet?

struct Node {
  int data;
  Node* next;
};

int main() {
  Node a{1, nullptr};
  Node b{2, &a};
  Node* head = &b;
  while (head) {
    std::cout << head->data << " ";
    head = head->next;
  }
  return 0;
}

medium

A. 1

B. 1 2

C. 2 1

D. 2

Solution

1. Step 1: Understand node linking

   Node b points to a, so list order is b -> a.

2. Step 2: Trace the while loop output

   Prints b.data (2), then a.data (1), then nullptr ends loop.

3. Final Answer:

   2 1 -> Option C

4. Quick Check:

   Linked list prints 2 then 1 [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Assuming order is a then b
• Confusing pointer directions
• Printing only first node

4. Identify the error in this code snippet that tries to create a tree node in C++:

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

int main() {
  TreeNode root;
  root.val = 10;
  root.left = nullptr;
  root.right = nullptr;
  root.left->val = 5;
  return 0;
}

medium

A. Dereferencing nullptr in root.left->val

B. Missing semicolon after struct definition

C. Incorrect pointer declaration for left and right

D. root.val should be initialized with new keyword

Solution

1. Step 1: Analyze pointer initialization

   root.left is set to nullptr, so it points to nothing.

2. Step 2: Check pointer dereference

   Accessing root.left->val dereferences nullptr causing runtime error.

3. Final Answer:

   Dereferencing nullptr in root.left->val -> Option A

4. Quick Check:

   Cannot access member via nullptr [OK]

Hint: Never dereference nullptr pointers [OK]

Common Mistakes:

• Ignoring nullptr before dereference
• Thinking struct needs semicolon error
• Confusing pointer declaration syntax

5. You want to store a company's organizational chart where each employee can have multiple subordinates. Which data structure is best and why? A) Array because it stores data contiguously B) Tree because it naturally models multiple children per node C) Linked List because it allows dynamic size D) Stack because it supports last-in-first-out access

hard

A. Tree because it naturally models multiple children per node

B. Array because it stores data contiguously

C. Linked List because it allows dynamic size

D. Stack because it supports last-in-first-out access

Solution

1. Step 1: Understand organizational chart structure

   Each employee can have multiple subordinates, forming a hierarchy with multiple children per node.

2. Step 2: Match data structure to hierarchy with multiple children

   Trees allow nodes to have multiple children, perfect for this use case. Arrays and linked lists are linear, stacks are LIFO.

3. Final Answer:

   Tree because it naturally models multiple children per node -> Option A

4. Quick Check:

   Multiple children per node means Tree [OK]

Hint: Multiple children? Use Tree for hierarchy [OK]

Common Mistakes:

• Choosing Array for hierarchy
• Choosing Linked List for multiple children
• Confusing Stack with hierarchical needs