Tree vs Array vs Linked List When Hierarchy Matters in DSA Rust - 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 name and may have subordinates reporting to them. You want to represent this hierarchy in code to easily see who reports to whom.

🎯 Goal: You will create a simple employee hierarchy using a tree structure in Rust. You will then explore how arrays and linked lists differ when representing hierarchical data.

📋 What You'll Learn

Create a struct called Employee with a name field and a subordinates field which is a vector of Employee.

Create a root employee with two subordinates.

Create an array of employee names representing a flat list.

Create a linked list of employee names representing a chain of command.

Print the tree hierarchy, the array, and the linked list.

💡 Why This Matters

🌍 Real World

Hierarchical data structures like trees are used in organizational charts, file systems, and menus where parent-child relationships matter.

💼 Career

Understanding when to use trees, arrays, or linked lists helps software engineers design efficient data models for complex data.

1

Create the Employee struct and root employee with subordinates

Create a struct called Employee with a name field of type String and a subordinates field which is a Vec. Then create a variable called ceo of type Employee with the name "Alice" and two subordinates named "Bob" and "Charlie" with no subordinates.

DSA Rust

// Define Employee struct and create ceo with two subordinates
// Your code here

Hint

Use struct to define Employee. Use Vec for subordinates. Create ceo with name and subordinates fields.

2

Create an array of employee names representing a flat list

Below the ceo variable, create a variable called employee_names which is an array of &str containing exactly these names in order: "Alice", "Bob", "Charlie".

DSA Rust

struct Employee {
    name: String,
    subordinates: Vec,
}

fn main() {
    let ceo = Employee {
        name: String::from("Alice"),
        subordinates: vec![
            Employee {
                name: String::from("Bob"),
                subordinates: vec![],
            },
            Employee {
                name: String::from("Charlie"),
                subordinates: vec![],
            },
        ],
    };

    // Create an array called employee_names with "Alice", "Bob", "Charlie"
    // Your code here
}

Hint

Use a fixed-size array with type [&str; 3] and assign the names in order.

3

Create a linked list of employee names representing a chain of command

Below the employee_names array, create a singly linked list of employee names representing a chain of command: Alice -> Bob -> Charlie. Define an enum called List with variants Node containing a String and a Box<List>, and Nil for the end. Then create a variable called chain of type List representing this chain.

DSA Rust

struct Employee {
    name: String,
    subordinates: Vec,
}

// Define List enum here
// Your code here

fn main() {
    let ceo = Employee {
        name: String::from("Alice"),
        subordinates: vec![
            Employee {
                name: String::from("Bob"),
                subordinates: vec![],
            },
            Employee {
                name: String::from("Charlie"),
                subordinates: vec![],
            },
        ],
    };

    let employee_names: [&str; 3] = ["Alice", "Bob", "Charlie"];

    // Create linked list chain: Alice -> Bob -> Charlie
    // Your code here
}

Hint

Define List enum with Node and Nil. Create chain by nesting Node variants with Box.

4

Print the tree hierarchy, the array, and the linked list

Add code inside main to print the employee hierarchy tree starting from ceo with indentation for subordinates, print the employee_names array as a comma-separated list, and print the linked list chain names separated by arrows ->. Use a helper function print_tree that takes an &Employee and an indentation level usize to print the tree. Also create a helper function print_chain that takes a reference to List and prints the chain.

DSA Rust

struct Employee {
    name: String,
    subordinates: Vec,
}

enum List {
    Node(String, Box),
    Nil,
}

// Define print_tree function
// Define print_chain function

fn main() {
    let ceo = Employee {
        name: String::from("Alice"),
        subordinates: vec![
            Employee {
                name: String::from("Bob"),
                subordinates: vec![],
            },
            Employee {
                name: String::from("Charlie"),
                subordinates: vec![],
            },
        ],
    };

    let employee_names: [&str; 3] = ["Alice", "Bob", "Charlie"];

    let chain = List::Node(
        String::from("Alice"),
        Box::new(List::Node(
            String::from("Bob"),
            Box::new(List::Node(String::from("Charlie"), Box::new(List::Nil))),
        )),
    );

    // Print the tree hierarchy
    // Print the employee_names array
    // Print the linked list chain
    // Your code here
}

Hint

Use recursion to print the tree with indentation. Use join to print the array. Use pattern matching to print the linked list with arrows.

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