Tree vs Array vs Linked List When Hierarchy Matters in DSA C# - Trade-offs & Analysis

Mental Model

A tree shows clear parent-child links for hierarchy, arrays store items in order without hierarchy, and linked lists chain items linearly without branches.

Analogy: Think of a family tree (tree) showing parents and children, a photo album (array) with pictures in order, and a chain of paper clips (linked list) connected one after another.

Tree:
    1
   / \
  2   3
 / \
4   5

Array:
[1][2][3][4][5]

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Tree with nodes 1 as root, 2 and 3 as children of 1, 4 and 5 as children of 2; Array with elements [1,2,3,4,5]; Linked List with nodes 1->2->3->4->5

Goal: Show how hierarchy is represented differently in tree, array, and linked list

Step 1: Look at tree root node 1 with children 2 and 3

Tree:
    1 ↑
   / \
  2   3
 / \
4   5
Array:
[1][2][3][4][5]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Tree shows parent-child links clearly, unlike array or linked list

Step 2: Check children of node 2 in tree: nodes 4 and 5

Tree:
    1
   / \
  2 ↑  3
 / \
4   5
Array:
[1][2][3][4][5]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Tree branches show hierarchy deeper than linear structures

Step 3: Observe array elements stored sequentially without hierarchy

Tree:
    1
   / \
  2   3
 / \
4   5
Array:
[1 ↑][2][3][4][5]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Array stores data in order but does not show parent-child relationships

Step 4: Observe linked list nodes connected one after another

Tree:
    1
   / \
  2   3
 / \
4   5
Array:
[1][2][3][4][5]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 ↑ -> null

Why: Linked list shows linear connection but no branching hierarchy

Result:

Tree:
    1
   / \
  2   3
 / \
4   5
Array:
[1][2][3][4][5]
Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TreeNode {
    public int val;
    public List<TreeNode> children;
    public TreeNode(int val) {
        this.val = val;
        this.children = new List<TreeNode>();
    }
}

class LinkedListNode {
    public int val;
    public LinkedListNode next;
    public LinkedListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

class Program {
    static void PrintTree(TreeNode root, string indent = "") {
        if (root == null) return;
        Console.WriteLine(indent + root.val);
        foreach (var child in root.children) {
            PrintTree(child, indent + "  ");
        }
    }

    static void PrintArray(int[] arr) {
        Console.WriteLine("[" + string.Join(", ", arr) + "]");
    }

    static void PrintLinkedList(LinkedListNode head) {
        var curr = head;
        while (curr != null) {
            Console.Write(curr.val);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }

    static void Main() {
        // Build tree
        var root = new TreeNode(1);
        var node2 = new TreeNode(2);
        var node3 = new TreeNode(3);
        var node4 = new TreeNode(4);
        var node5 = new TreeNode(5);
        root.children.Add(node2);
        root.children.Add(node3);
        node2.children.Add(node4);
        node2.children.Add(node5);

        // Build array
        int[] arr = {1, 2, 3, 4, 5};

        // Build linked list
        var head = new LinkedListNode(1);
        head.next = new LinkedListNode(2);
        head.next.next = new LinkedListNode(3);
        head.next.next.next = new LinkedListNode(4);
        head.next.next.next.next = new LinkedListNode(5);

        Console.WriteLine("Tree:");
        PrintTree(root);
        Console.WriteLine("Array:");
        PrintArray(arr);
        Console.WriteLine("Linked List:");
        PrintLinkedList(head);
    }
}

root.children.Add(node2); root.children.Add(node3);

link children nodes 2 and 3 to root node 1 to build hierarchy

node2.children.Add(node4); node2.children.Add(node5);

link children nodes 4 and 5 to node 2 to extend hierarchy

while (curr != null) { Console.Write(curr.val); if (curr.next != null) Console.Write(" -> "); curr = curr.next; }

traverse linked list nodes one by one to print linear sequence

Console.WriteLine("[" + string.Join(", ", arr) + "]");

print array elements in order

foreach (var child in root.children) { PrintTree(child, indent + " "); }

recursively print each child with indentation to show hierarchy

Output

Tree:

1

  2

    4

    5

  3

Array:

[1, 2, 3, 4, 5]

Linked List:

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because each structure is printed by visiting each element once

Space: O(n) for storing all elements in each structure

vs Alternative: Tree uses extra space for child lists but shows hierarchy clearly; array uses contiguous memory but no hierarchy; linked list uses pointers but only linear order

Edge Cases

Empty tree, array, or linked list

Print functions handle null or empty inputs gracefully without errors

DSA C#

if (root == null) return;

Single element structures

Prints single node or element correctly showing minimal hierarchy or sequence

DSA C#

while (curr != null) { ... }

When to Use This Pattern

When a problem needs to represent parent-child relationships or hierarchy, use a tree; if order matters without hierarchy, use array or linked list.

Common Mistakes

Mistake: Trying to represent hierarchy using only arrays or linked lists without extra info
Fix: Use tree structure with explicit child links to capture hierarchy

Summary

Shows how tree, array, and linked list represent data differently when hierarchy matters

Use tree to represent hierarchical data, array or linked list for linear sequences

Hierarchy requires explicit parent-child links which only trees provide naturally

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