Tree vs Array vs Linked List When Hierarchy Matters in DSA Java - 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 handle hierarchical data.

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

📋 What You'll Learn

Create an array of employee names in hierarchical order

Create a singly linked list of employee names in hierarchical order

Create a simple tree structure with nodes representing employees and their direct reports

Print the hierarchy from each data structure clearly

💡 Why This Matters

🌍 Real World

Companies often need to represent organizational charts or file systems where hierarchy matters. Trees are the natural choice for such data.

💼 Career

Understanding how to represent and traverse hierarchical data structures is essential for software engineers working on databases, UI components, and system design.

1

Create an array of employees in hierarchy order

Create a String[] employees array with these exact values in order: "CEO", "Manager1", "Manager2", "Employee1", "Employee2".

DSA Java

// Create the employees array with given names
// Your code here

Hint

Use curly braces {} to list the employee names inside the array.

2

Create a singly linked list of employees

Add a class Node with a String name and a Node next. Then create Node head and link nodes with names: "CEO" → "Manager1" → "Manager2" → "Employee1" → "Employee2".

DSA Java

public class HierarchyDemo {
    static class Node {
        String name;
        Node next;
        Node(String name) {
            this.name = name;
            this.next = null;
        }
    }

    public static void main(String[] args) {
        String[] employees = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};
        // Create linked list nodes and link them
        // Your code here
    }
}

Hint

Create nodes one by one and link them using the next property.

3

Create a simple tree structure for employees

Add a class TreeNode with String name and List<TreeNode> children. Create the tree with TreeNode root named "CEO". Add "Manager1" and "Manager2" as children of root. Add "Employee1" as child of Manager1 and "Employee2" as child of Manager2.

DSA Java

import java.util.ArrayList;
import java.util.List;

public class HierarchyDemo {
    static class Node {
        String name;
        Node next;
        Node(String name) {
            this.name = name;
            this.next = null;
        }
    }

    static class TreeNode {
        String name;
        List children;
        TreeNode(String name) {
            this.name = name;
            this.children = new ArrayList();
        }
    }

    public static void main(String[] args) {
        String[] employees = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

        Node head = new Node("CEO");
        head.next = new Node("Manager1");
        head.next.next = new Node("Manager2");
        head.next.next.next = new Node("Employee1");
        head.next.next.next.next = new Node("Employee2");

        // Create tree nodes and build hierarchy
        // Your code here
    }
}

Hint

Use ArrayList to hold children nodes and add them to their parents.

4

Print the hierarchy from all data structures

Print the employees array elements separated by commas. Then print the linked list names in order separated by arrows " -> ". Finally, print the tree hierarchy starting from root with indentation for children (2 spaces per level). Use a helper method printTree(TreeNode node, int level) to print the tree.

DSA Java

import java.util.ArrayList;
import java.util.List;

public class HierarchyDemo {
    static class Node {
        String name;
        Node next;
        Node(String name) {
            this.name = name;
            this.next = null;
        }
    }

    static class TreeNode {
        String name;
        List children;
        TreeNode(String name) {
            this.name = name;
            this.children = new ArrayList();
        }
    }

    public static void main(String[] args) {
        String[] employees = {"CEO", "Manager1", "Manager2", "Employee1", "Employee2"};

        Node head = new Node("CEO");
        head.next = new Node("Manager1");
        head.next.next = new Node("Manager2");
        head.next.next.next = new Node("Employee1");
        head.next.next.next.next = new Node("Employee2");

        TreeNode root = new TreeNode("CEO");
        TreeNode manager1 = new TreeNode("Manager1");
        TreeNode manager2 = new TreeNode("Manager2");
        root.children.add(manager1);
        root.children.add(manager2);
        manager1.children.add(new TreeNode("Employee1"));
        manager2.children.add(new TreeNode("Employee2"));

        // Print array, linked list, and tree
        // Your code here
    }

    // Add printTree method here
}

Hint

Use loops to print the array and linked list. Use recursion with indentation to print the tree.

Practice

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

easy

A. Tree

B. Array

C. Linked List

D. Stack

Solution

1. Step 1: Understand hierarchy representation

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

2. Step 2: Compare with other structures

   Arrays and linked lists are linear and do not represent branching relationships well.

3. Final Answer:

   Tree -> Option A

4. Quick Check:

   Hierarchy = Tree [OK]

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

Common Mistakes:

• Choosing Array because it stores elements
• Choosing Linked List thinking it can represent hierarchy
• Confusing Stack with hierarchical structure

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

easy

A. array int arr = new int[5];

B. int arr = new int[5];

C. int arr[] = new int();

D. int[] arr = new int[5];

Solution

1. Step 1: Check Java array syntax

   Java arrays are declared with type[], variable name, and size using new keyword.

2. Step 2: Validate each option

   int[] arr = new int[5]; matches correct syntax: int[] arr = new int[5]; others have syntax errors.

3. Final Answer:

   int[] arr = new int[5]; -> Option D

4. Quick Check:

   Java array declaration = int[] arr = new int[5]; [OK]

Hint: Remember Java arrays use type[] name = new type[size]; [OK]

Common Mistakes:

• Missing [] after type
• Using parentheses instead of brackets
• Incorrect keyword 'array'

3. You want to store employee hierarchy where each employee can have multiple subordinates. Which data structure is best and why?

easy

A. Array, because it stores elements in order

B. Linked List, because it links employees one after another

C. Tree, because it models multiple children per node

D. Stack, because it manages last-in-first-out order

Solution

1. Step 1: Understand employee hierarchy needs

   Each employee can have multiple subordinates, so structure must support multiple children per node.

2. Step 2: Evaluate data structures

   Array and linked list are linear, stack is LIFO. Only tree supports multiple children naturally.

3. Final Answer:

   Tree, because it models multiple children per node -> Option C

4. Quick Check:

   Multiple children = Tree [OK]

Hint: Multiple children per node? Choose Tree [OK]

Common Mistakes:

• Choosing Array or Linked List for hierarchical data
• Confusing Stack with hierarchy management
• Ignoring multiple children requirement

4. What will be the output of the following Java code snippet?

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

public class Test {
  public static void main(String[] args) {
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    Node current = head;
    while(current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.print("null");
  }
}

medium

A. 1 -> 2 -> 3 -> null

B. 1 2 3 null

C. null -> 1 -> 2 -> 3

D. 1 -> 3 -> 2 -> null

Solution

1. Step 1: Trace linked list creation

   Nodes created with values 1, 2, 3 linked in order: 1 -> 2 -> 3.

2. Step 2: Trace print loop

   Loop prints each node's data followed by ' -> ', ends with 'null'. Output is '1 -> 2 -> 3 -> null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Linked list print = 1 -> 2 -> 3 -> null [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Mixing node order
• Missing 'null' at end
• Printing values without arrows

5. Identify the error in this Java code that tries to create a simple tree node:

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) {
    val = v;
    left = null;
    right = null;
  }
}

public class Main {
  public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(15);
    root.left.left = 7;
  }
}

medium

A. Missing semicolon after TreeNode declarations

B. Assigning integer 7 directly to left.left instead of TreeNode

C. Incorrect constructor name in TreeNode class

D. Using 'root' without initialization

Solution

1. Step 1: Analyze assignment to left.left

   left.left expects a TreeNode object but is assigned integer 7 directly, causing type error.

2. Step 2: Check other code parts

   Constructor name and semicolons are correct; root is initialized properly.

3. Final Answer:

   Assigning integer 7 directly to left.left instead of TreeNode -> Option B

4. Quick Check:

   TreeNode fields need TreeNode objects, not int [OK]

Hint: Tree nodes must link to nodes, not raw values [OK]

Common Mistakes:

• Assigning raw values to node references
• Ignoring type mismatch errors
• Assuming automatic conversion from int to TreeNode