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

Mental Model

A tree shows clear parent-child links for hierarchy, arrays store items in order but no 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 paperclips (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 each structure represents hierarchy or order and what happens when we want to find children of node 2

Step 1: Look for children of node 2 in the tree

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

Why: In tree, node 2 has direct links to children 4 and 5

Step 2: Look for children of node 2 in the array by scanning elements after 2

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

Why: Array stores elements in order but no hierarchy, so children are not directly linked

Step 3: Look for children of node 2 in the linked list by traversing nodes after 2

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

Why: Linked list is linear, no branches, so no direct children of 2

Step 4: Identify children of node 2 in tree as 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 structure explicitly stores hierarchy with pointers to children

Result:

Tree shows children of 2 as 4 and 5 directly linked
Array and Linked List do not show hierarchy, only order

Annotated Code

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

public class HierarchyDemo {
    public static void main(String[] args) {
        // Build tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

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

        // Build linked list
        LinkedListNode 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);

        // Find children of node 2 in tree
        System.out.print("Tree children of 2: ");
        printTreeChildren(root, 2);

        // Find children of node 2 in array
        System.out.print("Array children of 2: ");
        printArrayChildren(arr, 2);

        // Find children of node 2 in linked list
        System.out.print("Linked List children of 2: ");
        printLinkedListChildren(head, 2);
    }

    static void printTreeChildren(TreeNode node, int target) {
        if (node == null) return;
        if (node.val == target) {
            if (node.left != null) System.out.print(node.left.val + " ");
            if (node.right != null) System.out.print(node.right.val + " ");
            System.out.println();
            return;
        }
        printTreeChildren(node.left, target);
        printTreeChildren(node.right, target);
    }

    static void printArrayChildren(int[] arr, int target) {
        // No hierarchy, so no children
        System.out.println("None");
    }

    static void printLinkedListChildren(LinkedListNode head, int target) {
        // No hierarchy, so no children
        System.out.println("None");
    }
}

if (node.val == target) {

Check if current node is the target to find children

if (node.left != null) System.out.print(node.left.val + " ");

Print left child if exists

if (node.right != null) System.out.print(node.right.val + " ");

Print right child if exists

System.out.println("None");

Print None for no children in array or linked list

Output

Tree children of 2: 4 5 

Array children of 2: None

Linked List children of 2: None

Complexity Analysis

Time: O(n) because we may need to traverse all nodes in the tree to find the target

Space: O(h) where h is tree height due to recursion stack; O(1) for array and linked list since no hierarchy

vs Alternative: Tree allows direct child access via pointers, arrays and linked lists require scanning or do not support hierarchy

Edge Cases

Empty tree

No children found, no output

DSA Java

if (node == null) return;

Target node not in tree

No children printed

DSA Java

if (node == null) return;

Array or linked list with no hierarchy

Always prints None

DSA Java

System.out.println("None");

When to Use This Pattern

When a problem involves parent-child relationships or hierarchy, think of using a tree because arrays and linked lists do not represent hierarchy well.

Common Mistakes

Mistake: Trying to find children in an array or linked list as if they have hierarchy
Fix: Remember arrays and linked lists only store order, not parent-child links

Mistake: Assuming linked list nodes can have multiple children
Fix: Linked lists are linear; use trees for branching hierarchy

Summary

Shows how trees represent hierarchy with parent-child links, unlike arrays or linked lists.

Use trees when you need to model relationships with branches and levels.

The key insight is that only trees have explicit pointers to children, arrays and linked lists do not.

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