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, and some employees manage others. You want to represent this hierarchy in different ways to understand how data structures handle relationships.

🎯 Goal: You will create three data structures: an array, a linked list, and a tree to represent employees and their managers. You will then print the structure to see how hierarchy is shown differently in each.

📋 What You'll Learn

Create an array of employee names

Create a linked list of employee names

Create a simple tree structure with employees and their direct reports

Print each data structure to show the hierarchy or order

💡 Why This Matters

🌍 Real World

Companies often need to represent organizational charts or file systems where hierarchy matters. Trees are natural for this, while arrays and linked lists show simpler linear relationships.

💼 Career

Understanding these data structures helps in software development roles involving data organization, UI trees, databases, and more.

1

Create an array of employee names

Create a char* array called employees with these exact names: "CEO", "Manager1", "Manager2", "Employee1", "Employee2".

DSA C

# Create the array of employee names
// Your code here

Hint

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

2

Create a linked list of employee names

Define a struct Node with a char* name and a pointer next. Then create three nodes named CEO, Manager1, and Employee1 linked in that order.

DSA C

#include 

char* employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

// Define struct Node and create linked list nodes CEO -> Manager1 -> Employee1
// Your code here

int main() {
    return 0;
}

Hint

Define the struct with char* name and struct Node* next. Create nodes and link them by setting next pointers.

3

Create a simple tree structure for employee hierarchy

Define a struct TreeNode with a char* name, an array of pointers children of size 2, and an int child_count. Create nodes for CEO, Manager1, and Manager2. Set CEO as parent of Manager1 and Manager2.

DSA C

#include 
#include 

char* employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

typedef struct Node {
    char* name;
    struct Node* next;
} Node;

Node CEO = {"CEO", NULL};
Node Manager1 = {"Manager1", NULL};
Node Employee1 = {"Employee1", NULL};

// Define struct TreeNode and create CEO with Manager1 and Manager2 as children
// Your code here

int main() {
    CEO.next = &Manager1;
    Manager1.next = &Employee1;
    return 0;
}

Hint

Define TreeNode with name, children array, and child_count. Create nodes and assign children to CEO.

4

Print all three data structures

Print the array employees in order. Then print the linked list starting from &CEO by following next. Finally, print the tree starting from &CEONode showing CEO and its children indented.

DSA C

#include 
#include 

char* employees[] = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

typedef struct Node {
    char* name;
    struct Node* next;
} Node;

Node CEO = {"CEO", NULL};
Node Manager1 = {"Manager1", NULL};
Node Employee1 = {"Employee1", NULL};

typedef struct TreeNode {
    char* name;
    struct TreeNode* children[2];
    int child_count;
} TreeNode;

TreeNode Manager1Node = {"Manager1", {NULL, NULL}, 0};
TreeNode Manager2Node = {"Manager2", {NULL, NULL}, 0};
TreeNode CEONode = {"CEO", {&Manager1Node, &Manager2Node}, 2};

int main() {
    CEO.next = &Manager1;
    Manager1.next = &Employee1;

    // Print array employees
    // Print linked list starting from &CEO
    // Print tree starting from &CEONode with indentation
    // Your code here

    return 0;
}

Hint

Use a loop to print the array. Use a while loop to print the linked list by following next. Use a recursive function to print the tree with indentation.

Practice

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

easy

A. Stack

B. Array

C. Tree

D. Linked List

Solution

1. Step 1: Understand hierarchy representation

   Hierarchies have parent-child relationships, which trees represent naturally with nodes and branches.

2. Step 2: Compare with other structures

   Arrays and linked lists are linear and do not represent multiple branches from one node easily.

3. Final Answer:

   Tree -> Option C

4. Quick Check:

   Hierarchy = Tree [OK]

Hint: Hierarchy means branching; trees model branching best [OK]

Common Mistakes:

• Choosing array because it stores elements
• Choosing linked list assuming it can represent hierarchy
• Confusing stack with hierarchical structure

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

easy

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

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

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

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

Solution

1. Step 1: Check pointer usage in struct

   A linked list node must have a pointer to the next node, so 'struct Node* next' is correct.

2. Step 2: Identify incorrect declarations

   Options B, C, and D either use wrong types or missing pointers, causing errors.

3. Final Answer:

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

4. Quick Check:

   Pointer to next node = struct Node { int data; struct Node* next; }; [OK]

Hint: Linked list nodes need pointer to next node [OK]

Common Mistakes:

• Using int instead of pointer for next
• Omitting struct keyword in C
• Using struct Node next instead of pointer

3. What will be the output of the following C code that builds a simple 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;
}

medium

A. Garbage value

B. 0

C. Compilation error

D. 10

Solution

1. Step 1: Analyze struct initialization

   The root node is initialized with data=10 and left/right pointers as NULL.

2. Step 2: Check printf output

   Printing root.data will output 10 as assigned.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   root.data = 10 [OK]

Hint: Initialized struct fields print assigned values [OK]

Common Mistakes:

• Assuming uninitialized pointers affect data
• Expecting compilation error due to typedef
• Confusing pointer and value printing

4. Identify the error in this linked list insertion code snippet in C:

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

void insertAtFront(struct Node* head, int val) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = val;
  newNode->next = head;
  head = newNode;
}

medium

A. malloc size is incorrect

B. head is passed by value; changes won't affect original list

C. newNode->next should be NULL

D. Missing free() for old head

Solution

1. Step 1: Understand pointer passing in C

   head is passed by value, so assigning head = newNode only changes local copy.

2. Step 2: Effect on original list

   The original head pointer outside the function remains unchanged, so insertion fails.

3. Final Answer:

   head is passed by value; changes won't affect original list -> Option B

4. Quick Check:

   Pointer passed by value = head is passed by value; changes won't affect original list [OK]

Hint: Pass pointer by reference to modify original list [OK]

Common Mistakes:

• Thinking malloc size is wrong
• Assuming newNode->next must be NULL
• Confusing free() necessity here

5. You need to store a company's organizational chart where each manager can have multiple direct reports. Which data structure is best and why?

hard

A. Tree because it models hierarchical parent-child relationships

B. Linked List because it allows dynamic size

C. Array because it stores elements contiguously

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

Solution

1. Step 1: Understand organizational chart structure

   It is a hierarchy where managers have multiple direct reports (children).

2. Step 2: Match data structure to hierarchy

   Trees naturally represent such parent-child relationships with multiple branches.

3. Step 3: Evaluate other options

   Arrays and linked lists are linear and do not represent multiple children per node well; stacks are for LIFO access, not hierarchy.

4. Final Answer:

   Tree because it models hierarchical parent-child relationships -> Option A

5. Quick Check:

   Hierarchy with multiple children = Tree [OK]

Hint: Multiple children per node? Use tree structure [OK]

Common Mistakes:

• Choosing array for hierarchy
• Confusing linked list dynamic size with hierarchy
• Using stack for hierarchical data