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.