Tree vs Array vs Linked List When Hierarchy Matters in DSA Java - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Traversing a Simple Tree Structure

Consider this Java code that builds a simple tree and prints node values in preorder (root, left, right). What is the printed output?

DSA Java

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

public class Main {
    public static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        preorder(root);
    }
}

A 1 2 4 5 3

B 1 3 2 4 5

C 4 2 5 1 3

D 2 4 5 1 3

💡 Hint

Preorder traversal visits root first, then left subtree, then right subtree.

Preorder traversal prints the root node first, then recursively visits the left subtree, then the right subtree. So the order is 1 (root), then 2 (left child), then 4 (left-left child), then 5 (left-right child), then 3 (right child).

🧠 Conceptual

intermediate

Choosing Data Structure for Hierarchical Data

Which data structure is best suited to represent hierarchical data with parent-child relationships and efficient traversal?

A Array

B Linked List

C Stack

D Tree

💡 Hint

Think about how hierarchy and multiple children per node are represented.

Trees naturally represent hierarchical data with nodes connected to multiple children. Arrays and linked lists are linear and do not represent hierarchy well. Stacks are for LIFO order, not hierarchy.

❓ Predict Output

advanced

Output of Linked List vs Array Representation

Given these two Java snippets representing the same sequence of values, what is the output after adding 10 at the end?

DSA Java

/* Linked List version */
class Node {
    int val;
    Node next;
    Node(int v) { val = v; }
}

public class Main {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        Node curr = head;
        while (curr.next != null) curr = curr.next;
        curr.next = new Node(10);
        curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}

/* Array version */
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int[] newArr = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) newArr[i] = arr[i];
        newArr[newArr.length - 1] = 10;
        for (int v : newArr) System.out.print(v + " ");
    }
}

A 1 2 3

B 10 1 2 3

C 1 2 3 10

D 1 2 10 3

💡 Hint

Both add 10 at the end of the sequence.

Both linked list and array versions add 10 at the end. The output prints the sequence with 10 appended last.

🔧 Debug

advanced

Identify the Error in Tree Node Insertion

This Java code tries to insert a new node as the left child of the root but causes a runtime error. What is the error?

DSA Java

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

public class Main {
    public static void main(String[] args) {
        Node root = null;
        root.left = new Node(5);
        System.out.println(root.left.val);
    }
}

A NullPointerException at root.left assignment

B Compilation error: cannot assign to root.left

C No error, prints 5

D ArrayIndexOutOfBoundsException

💡 Hint

Check if root is initialized before accessing its fields.

root is null, so accessing root.left causes NullPointerException at runtime.

🧠 Conceptual

expert

Hierarchy Representation Efficiency

Which data structure provides the most efficient way to represent a hierarchy with frequent insertions and deletions of nodes at arbitrary positions?

A Array with fixed size

B Tree with parent and child pointers

C Doubly Linked List

D Singly Linked List

💡 Hint

Consider how hierarchy and arbitrary insertions/deletions are handled.

Trees with parent and child pointers allow efficient insertions and deletions anywhere in the hierarchy, preserving structure. Arrays are fixed size and costly to resize. Linked lists are linear and do not represent hierarchy well.

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