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 like arrays, linked lists, and trees work when showing relationships.

🎯 Goal: You will create three different data structures to represent the employee hierarchy: an array, a linked list, and a tree. Then, you will print the hierarchy to see how each structure shows the relationships.

📋 What You'll Learn

Create an array of employee names in order of hierarchy

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

Create a tree where each node contains an employee name and a list of direct reports

Print the contents of each data structure to show the hierarchy

💡 Why This Matters

🌍 Real World

Hierarchies like company structures, file systems, and family trees are often represented using trees, arrays, or linked lists depending on the need.

💼 Career

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

1

Create an array of employees

Create a string array called employees with these exact values in order: "CEO", "Manager", "Lead", "Developer"

DSA C#

// Your code here

Hint

Use string[] employees = { ... }; to create the array with the exact names.

2

Create a linked list of employees

Create a class called EmployeeNode with a string Name property and an EmployeeNode Next property. Then create linked nodes for "CEO", "Manager", "Lead", and "Developer" linked in that order. Store the first node in a variable called head.

DSA C#

string[] employees = { "CEO", "Manager", "Lead", "Developer" };
// Your code here

Hint

Define the EmployeeNode class first, then link nodes by setting the Next property.

3

Create a tree of employees

Create a class called EmployeeTreeNode with a string Name property and a List<EmployeeTreeNode> Reports property. Create nodes for "CEO", "Manager", "Lead", and "Developer". Add Manager as a report to CEO, Lead as a report to Manager, and Developer as a report to Lead. Store the root node in a variable called root.

DSA C#

string[] employees = { "CEO", "Manager", "Lead", "Developer" };

class EmployeeNode
{
    public string Name;
    public EmployeeNode Next;
    public EmployeeNode(string name) { Name = name; Next = null; }
}

EmployeeNode head = new EmployeeNode("CEO");
head.Next = new EmployeeNode("Manager");
head.Next.Next = new EmployeeNode("Lead");
head.Next.Next.Next = new EmployeeNode("Developer");

// Your code here

Hint

Use a list to hold reports and add child nodes to represent the hierarchy.

4

Print all three structures

Print the employees array elements separated by ' -> '. Then print the linked list starting from head by traversing Next and printing names separated by ' -> '. Finally, print the tree starting from root using a recursive method called PrintTree that prints each employee name with indentation for hierarchy levels.

DSA C#

string[] employees = { "CEO", "Manager", "Lead", "Developer" };

class EmployeeNode
{
    public string Name;
    public EmployeeNode Next;
    public EmployeeNode(string name) { Name = name; Next = null; }
}

EmployeeNode head = new EmployeeNode("CEO");
head.Next = new EmployeeNode("Manager");
head.Next.Next = new EmployeeNode("Lead");
head.Next.Next.Next = new EmployeeNode("Developer");

class EmployeeTreeNode
{
    public string Name;
    public List Reports;
    public EmployeeTreeNode(string name) { Name = name; Reports = new List(); }
}

EmployeeTreeNode root = new EmployeeTreeNode("CEO");
EmployeeTreeNode manager = new EmployeeTreeNode("Manager");
EmployeeTreeNode lead = new EmployeeTreeNode("Lead");
EmployeeTreeNode developer = new EmployeeTreeNode("Developer");

root.Reports.Add(manager);
manager.Reports.Add(lead);
lead.Reports.Add(developer);

// Your code here

Hint

Use string.Join for the array, a while loop for the linked list, and a recursive method for the tree.

Practice

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

easy

A. Linked List

B. Array

C. Tree

D. Stack

Solution

1. Step 1: Identify best structure for hierarchical relationships

   Hierarchies have parent-child relationships, which are naturally modeled by trees. Arrays and linked lists are linear and do not represent branching well, unlike trees.

2. Final Answer:

   Tree -> Option C

3. Quick Check:

   Hierarchy = Tree [OK]

Hint: Hierarchy means branching, so choose Tree [OK]

Common Mistakes:

• Choosing Array because it's simple
• Choosing Linked List thinking it can branch
• Confusing Stack with hierarchical structure

2. Which of the following is the correct way to declare a simple array of integers in C#?

easy

A. int[] numbers = new int[5];

B. int numbers = new int[5];

C. int numbers[] = new int(5);

D. array numbers = int[5];

Solution

1. Step 1: Recall and verify C# array declaration syntax

   Arrays are declared with type[], variable name, and new type[size]. int[] numbers = new int[5]; matches; others have syntax errors.

2. Final Answer:

   int[] numbers = new int[5]; -> Option A

3. Quick Check:

   C# array syntax = int[] numbers = new int[5]; [OK]

Hint: Remember C# arrays use type[] variable = new type[size]; [OK]

Common Mistakes:

• Missing [] after type
• Using parentheses instead of brackets
• Incorrect variable declaration without type[]

3. Consider the following C# code that creates a simple tree node class and adds children:

using System;
using System.Collections.Generic;
class Node {
  public string Name;
  public List<Node> Children = new List<Node>();
  public Node(string name) { Name = name; }
}

var root = new Node("Root");
var child1 = new Node("Child1");
var child2 = new Node("Child2");
root.Children.Add(child1);
root.Children.Add(child2);
Console.WriteLine(root.Children[1].Name);

What will be printed?

medium

A. "Child1"

B. Runtime error

C. "Root"

D. "Child2"

Solution

1. Step 1: Trace list indexing and code execution

   Children list: index 0=Child1, index 1=Child2. root.Children[1].Name = "Child2".

2. Final Answer:

   "Child2" -> Option D

3. Quick Check:

   Index 1 child name = "Child2" [OK]

Hint: List index 1 means second child, so output is Child2 [OK]

Common Mistakes:

• Confusing index 0 and 1
• Thinking root's name prints
• Expecting runtime error due to list usage

4. The following C# code attempts to create a linked list node and link two nodes:

using System;
class Node {
  public int Value;
  public Node Next;
  public Node(int val) { Value = val; }
}

Node first = new Node(1);
Node second = new Node(2);
first.Next = second;
second.Next = first;
Console.WriteLine(first.Next.Next.Value);

What is the problem with this code?

medium

A. It causes a null reference exception

B. It creates a circular linked list causing infinite loops

C. It does not link nodes correctly

D. It will not compile due to syntax errors

Solution

1. Step 1: Analyze node linking and consequences

   first.Next=second; second.Next=first forms a circular list, causing infinite loops if traversed without checks.

2. Final Answer:

   It creates a circular linked list causing infinite loops -> Option B

3. Quick Check:

   Circular link = infinite loop risk [OK]

Hint: Check if Next points back to previous node causing loops [OK]

Common Mistakes:

• Assuming null reference error
• Thinking nodes are not linked
• Ignoring circular reference issues

5. You need to store a company's organizational chart where each employee can have multiple subordinates, and you want to quickly find an employee's manager. Which data structure combination is best to represent this hierarchy efficiently in C#?

hard

A. Use a tree where each node has a list of children and a reference to its parent node

B. Use an array of employees with indexes representing hierarchy levels

C. Use a singly linked list where each node points to the next employee

D. Use a stack to push and pop employees as you traverse the hierarchy

Solution

1. Step 1: Match requirements to data structure features

   Multiple subordinates (children list) + quick manager lookup (parent ref) = tree with bidirectional links. Others lack branching or parent access.

2. Final Answer:

   Use a tree where each node has a list of children and a reference to its parent node -> Option A

3. Quick Check:

   Parent and children links = Tree with parent ref [OK]

Hint: Parent and children links need tree nodes with parent pointers [OK]

Common Mistakes:

• Choosing array which lacks parent info
• Using linked list which is linear only
• Confusing stack usage with storage