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.