Tree vs Array vs Linked List When Hierarchy Matters in DSA C++ - Build Both Approaches

Tree vs Array vs Linked List When Hierarchy Matters

📖 Scenario: Imagine you are organizing a company's employee structure. Each employee has a manager, except the CEO. You want to represent this hierarchy in different ways to understand how data structures handle parent-child relationships.

🎯 Goal: You will create three data structures: an array, a linked list, and a tree to represent the employee hierarchy. Then, you will print the hierarchy from the tree to see how it naturally shows parent-child relationships.

📋 What You'll Learn

Create an array of employee names in order of their IDs

Create a linked list where each node contains an employee name and a pointer to the next employee

Create a tree structure where each node contains an employee name and pointers to their direct reports

Print the tree hierarchy showing each employee and their direct reports

💡 Why This Matters

🌍 Real World

Hierarchical data like company structures, file systems, and organization charts are best represented with trees to show parent-child relationships clearly.

💼 Career

Understanding how to choose and implement data structures for hierarchical data is essential for software developers working on databases, UI components, and system design.

1

Create an array of employees

Create a std::string array called employees with these exact names in order: "CEO", "Manager1", "Manager2", "Employee1", "Employee2".

DSA C++

// Your code here

Hint

Use std::string employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"}; to create the array.

2

Create a linked list of employees

Define a struct called Node with a std::string name and a Node* pointer called next. Then create nodes for each employee in this order: "CEO", "Manager1", "Manager2", "Employee1", "Employee2", linking them in a list starting with head.

DSA C++

#include 
#include 

std::string employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

// Your code here

Hint

Define the Node struct and create linked nodes for each employee, linking them with next.

3

Create a tree structure for the hierarchy

Define a struct called TreeNode with a std::string name and a std::vector<TreeNode*> called children. Create nodes for "CEO", "Manager1", "Manager2", "Employee1", and "Employee2". Add Manager1 and Manager2 as children of CEO. Add Employee1 as a child of Manager1 and Employee2 as a child of Manager2. Store the root in root.

DSA C++

#include 
#include 
#include 

std::string employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

struct Node {
    std::string name;
    Node* next;
};

Node* head = new Node{"CEO", nullptr};
head->next = new Node{"Manager1", nullptr};
head->next->next = new Node{"Manager2", nullptr};
head->next->next->next = new Node{"Employee1", nullptr};
head->next->next->next->next = new Node{"Employee2", nullptr};

// Your code here

Hint

Use std::vector<TreeNode*> to hold children and link nodes to form the hierarchy.

4

Print the tree hierarchy

Write a recursive function called printTree that takes a TreeNode* and an int level (default 0). It prints the node's name with indentation of two spaces per level, then calls itself on each child with level + 1. Call printTree(root) to display the hierarchy.

DSA C++

#include 
#include 
#include 

std::string employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

struct Node {
    std::string name;
    Node* next;
};

Node* head = new Node{"CEO", nullptr};
head->next = new Node{"Manager1", nullptr};
head->next->next = new Node{"Manager2", nullptr};
head->next->next->next = new Node{"Employee1", nullptr};
head->next->next->next->next = new Node{"Employee2", nullptr};

struct TreeNode {
    std::string name;
    std::vector children;
};

TreeNode* root = new TreeNode{"CEO"};
TreeNode* manager1 = new TreeNode{"Manager1"};
TreeNode* manager2 = new TreeNode{"Manager2"};
TreeNode* employee1 = new TreeNode{"Employee1"};
TreeNode* employee2 = new TreeNode{"Employee2"};

root->children.push_back(manager1);
root->children.push_back(manager2);
manager1->children.push_back(employee1);
manager2->children.push_back(employee2);

// Write the printTree function and call it on root below

Hint

Use recursion to print each node's name with indentation based on the level.

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