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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tree Traversal in Rust

What is the output of this Rust code that performs a preorder traversal on a simple binary tree?

DSA Rust

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn preorder(&self, result: &mut Vec<i32>) {
        result.push(self.value);
        if let Some(ref left) = self.left {
            left.preorder(result);
        }
        if let Some(ref right) = self.right {
            right.preorder(result);
        }
    }
}

fn main() {
    let tree = Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    };
    let mut result = Vec::new();
    tree.preorder(&mut result);
    println!("{:?}", result);
}

A [1, 2, 3]

B [2, 1, 3]

C [3, 1, 2]

D [1, 3, 2]

💡 Hint

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

The preorder traversal visits nodes in the order: root, left child, right child. So the output is [1, 2, 3].

🧠 Conceptual

intermediate

Hierarchy Representation: Which Data Structure?

You need to represent a company's organizational chart where each employee can have multiple subordinates. Which data structure best models this hierarchy?

A Linked List

B Tree

C Array

D Stack

💡 Hint

Think about a structure that naturally represents parent-child relationships with multiple children.

A tree structure naturally models hierarchical data with multiple children per node, like an organizational chart.

🔧 Debug

advanced

Why Does This Linked List Code Cause a Runtime Error?

Consider this Rust code snippet for a singly linked list insertion. Why does it cause a runtime error?

DSA Rust

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn insert_at_head(head: &mut Option<Box<Node>>, val: i32) {
    let new_node = Box::new(Node { value: val, next: head.take() });
    *head = Some(new_node);
}

fn main() {
    let mut head = None;
    insert_at_head(&mut head, 10);
    insert_at_head(&mut head, 20);
    println!("{}", head.unwrap().next.unwrap().value);
}

A It panics because unwrap() is called on None

B It causes a stack overflow

C It prints 10 without error

D It causes a borrow checker error at compile time

💡 Hint

Check what unwrap() is called on and the list structure after insertions.

The list after two insertions has head value 20, and next node value 10. So unwrap().next.unwrap().value prints 10.

❓ Predict Output

advanced

Output of Array vs Linked List Insertions

What is the final state of the data structure after these operations? The data structure starts empty.

DSA Rust

let mut arr = vec![1, 2, 3];
arr.insert(1, 10);

let mut list = std::collections::LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
// list.insert_after = None; // (Note: This line is invalid and will cause error)
// Instead, assume we insert 10 after first element manually
// Final list elements: 1 -> 10 -> 2 -> 3

A Array: [1, 2, 10, 3], LinkedList: 1 -> 2 -> 10 -> 3 -> null

B Array: [1, 2, 3, 10], LinkedList: 1 -> 2 -> 3 -> 10 -> null

C Array: [10, 1, 2, 3], LinkedList: 10 -> 1 -> 2 -> 3 -> null

D Array: [1, 10, 2, 3], LinkedList: 1 -> 10 -> 2 -> 3 -> null

💡 Hint

Array insert shifts elements right; linked list insertion requires node reference.

Array insert at index 1 places 10 between 1 and 2. Linked list insertion after first element results in 1 -> 10 -> 2 -> 3.

🧠 Conceptual

expert

Choosing Data Structure for Dynamic Hierarchical Data

You must design a system to store a dynamic hierarchy where nodes can be added, removed, and moved frequently, and fast traversal is needed. Which data structure is best suited?

A HashMap with node IDs as keys and child lists as values

B Linked List of nodes with parent pointers

C Array with parent indices

D Tree with child lists and parent pointers

💡 Hint

Consider flexibility, fast lookup, and dynamic updates.

A HashMap keyed by node IDs with child lists allows fast lookup, easy addition/removal, and flexible hierarchy changes.

Practice

1. Which data structure is best to represent a hierarchy where each element can have multiple children, like a company organizational chart?

easy

A. Stack

B. Array

C. Linked List

D. Tree

Solution

1. Step 1: Understand hierarchy representation

   A hierarchy with multiple children per element needs a structure that can link one parent to many children.

2. Step 2: Compare data structures

   Arrays and linked lists are linear and do not naturally represent multiple children. Trees allow each node to have multiple children, fitting the hierarchy.

3. Final Answer:

   Tree -> Option D

4. Quick Check:

   Hierarchy with multiple children = Tree [OK]

Hint: Use trees for multi-child hierarchies, arrays for flat data [OK]

Common Mistakes:

• Choosing array for hierarchical data
• Using linked list which is linear
• Confusing stack with hierarchy

2. Which of the following Rust code snippets correctly declares a linked list node struct with a value and a next pointer?

easy

A. struct Node { value: i32, next: Option }

B. struct Node { value: i32, next: Node }

C. struct Node { value: i32, next: &Node }

D. struct Node { value: i32, next: Vec<Node> }

Solution

1. Step 1: Understand Rust linked list node

   Linked list nodes need a pointer to the next node. Rust uses Option for nullable heap pointers.

2. Step 2: Check each option

   A uses direct Node which causes infinite size error. C uses reference without lifetime. D uses Vec which is for multiple children, not linked list.

3. Final Answer:

   struct Node { value: i32, next: Option } -> Option A

4. Quick Check:

   Linked list node uses Option [OK]

Hint: Use Option for next pointer in Rust linked lists [OK]

Common Mistakes:

• Using direct Node type causing infinite size
• Using references without lifetimes
• Using Vec instead of single next pointer

3. What will be the output of this Rust code that builds a simple tree and prints the root's first child's value?

struct Node {
    value: i32,
    children: Vec<Node>,
}

fn main() {
    let child = Node { value: 10, children: vec![] };
    let root = Node { value: 5, children: vec![child] };
    println!("{}", root.children[0].value);
}

medium

A. 10

B. 5

C. 0

D. Compilation error

Solution

1. Step 1: Understand tree structure and initialization

   Root node has value 5 and one child with value 10 stored in a vector.

2. Step 2: Trace the print statement

   Printing root.children[0].value accesses the first child's value, which is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   root.children[0].value = 10 [OK]

Hint: Access first child value with root.children[0].value [OK]

Common Mistakes:

• Printing root.value instead of child's
• Confusing vector index
• Assuming compilation error due to struct

4. This Rust code tries to create a linked list but fails to compile. What is the main error?

struct Node {
    value: i32,
    next: Box<Node>,
}

fn main() {
    let node = Node { value: 1, next: Box::new(Node { value: 2, next: Box::new(Node { value: 3, next: None }) }) };
}

medium

A. Value type i32 is invalid

B. Missing Option for next pointer to allow None

C. Box cannot be used for recursive types

D. Syntax error in struct definition

Solution

1. Step 1: Identify recursive type issue

   Recursive types in Rust must use Option to allow end of list (None).

2. Step 2: Check code for missing Option

   Code uses Box<Node> without Option, so no way to represent end (None), causing compile error.

3. Final Answer:

   Missing Option for next pointer to allow None -> Option B

4. Quick Check:

   Recursive next pointer needs Option [OK]

Hint: Use Option for nullable next in linked list [OK]

Common Mistakes:

• Thinking Box alone handles recursion
• Blaming i32 type
• Assuming syntax error in struct

5. You want to represent a file system hierarchy in Rust where folders can contain files and other folders. Which data structure and Rust type combination is best suited for this?

hard

A. Array of strings

B. Linked list of file names

C. Tree with enum Node { File(String), Folder(Vec<Node>) }

D. HashMap with file paths as keys

Solution

1. Step 1: Understand file system hierarchy

   Folders can contain files and other folders, so a recursive structure is needed.

2. Step 2: Evaluate data structure options

   Array or linked list can't represent nested folders well. HashMap stores flat keys, not hierarchy. Tree with enum Node allows files and folders recursively.

3. Final Answer:

   Tree with enum Node { File(String), Folder(Vec<Node>) } -> Option C

4. Quick Check:

   Recursive enum tree fits file system hierarchy [OK]

Hint: Use recursive enum tree for nested folders and files [OK]

Common Mistakes:

• Using flat arrays or lists for nested folders
• Using HashMap which is flat key-value
• Not using enum to distinguish files and folders