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

Mental Model

When data has levels or branches, a tree shows the hierarchy clearly, arrays keep items in order but no levels, and linked lists chain items linearly.

Analogy: Think of a family tree (tree) showing parents and children, a photo album (array) with pictures in order, and a treasure hunt trail (linked list) where each clue leads to the next.

Tree:
    1
   / \
  2   3
 / \
4   5

Array:
[1][2][3][4][5]

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Data: 1 is parent of 2 and 3; 2 is parent of 4 and 5; show how tree, array, and linked list represent this

Goal: Understand how hierarchy is kept or lost in each structure

Step 1: Build tree with root 1 and children 2, 3; 2 has children 4, 5

Tree:
    1
   / \
  2   3
 / \
4   5

Why: Tree naturally shows parent-child relationships

Step 2: Put all nodes in an array in order: 1, 2, 3, 4, 5

Array:
[1][2][3][4][5]

Why: Array keeps order but no hierarchy info

Step 3: Link nodes in a list from 1 to 5 linearly

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked list shows sequence but no branching

Result:

Tree:
    1
   / \
  2   3
 / \
4   5

Array:
[1][2][3][4][5]

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

// Tree node with children
#[derive(Debug)]
struct TreeNode {
    val: i32,
    children: Vec<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(TreeNode { val, children: vec![] }))
    }
}

// Linked list node
#[derive(Debug)]
struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

// Print tree with indentation
fn print_tree(node: Rc<RefCell<TreeNode>>, depth: usize) {
    for _ in 0..depth {
        print!("  ");
    }
    println!("{}", node.borrow().val);
    for child in &node.borrow().children {
        print_tree(Rc::clone(child), depth + 1);
    }
}

// Print array
fn print_array(arr: &[i32]) {
    print!("[");
    for (i, val) in arr.iter().enumerate() {
        if i > 0 { print!(","); }
        print!("{}", val);
    }
    println!("]");
}

// Print linked list
fn print_linked_list(head: &Option<Box<ListNode>>) {
    let mut curr = head;
    while let Some(node) = curr {
        print!("{}", node.val);
        if node.next.is_some() {
            print!(" -> ");
        }
        curr = &node.next;
    }
    println!(" -> null");
}

fn main() {
    // Build tree
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);

    root.borrow_mut().children.push(Rc::clone(&node2));
    root.borrow_mut().children.push(Rc::clone(&node3));
    node2.borrow_mut().children.push(Rc::clone(&node4));
    node2.borrow_mut().children.push(Rc::clone(&node5));

    println!("Tree:");
    print_tree(Rc::clone(&root), 0);

    // Build array
    let arr = vec![1, 2, 3, 4, 5];
    println!("\nArray:");
    print_array(&arr);

    // Build linked list
    let mut head = Box::new(ListNode::new(1));
    let mut curr = &mut head;
    for &val in &[2, 3, 4, 5] {
        curr.next = Some(Box::new(ListNode::new(val)));
        curr = curr.next.as_mut().unwrap();
    }
    println!("\nLinked List:");
    print_linked_list(&Some(head));
}

root.borrow_mut().children.push(Rc::clone(&node2)); root.borrow_mut().children.push(Rc::clone(&node3));

attach children 2 and 3 to root 1 to build tree hierarchy

node2.borrow_mut().children.push(Rc::clone(&node4)); node2.borrow_mut().children.push(Rc::clone(&node5));

attach children 4 and 5 to node 2 to continue tree hierarchy

print_tree(Rc::clone(&root), 0);

recursively print tree with indentation to show hierarchy

let arr = vec![1, 2, 3, 4, 5]; print_array(&arr);

store nodes in array to show linear order without hierarchy

curr.next = Some(Box::new(ListNode::new(val))); curr = curr.next.as_mut().unwrap();

link nodes one by one to form linked list sequence

print_linked_list(&Some(head));

print linked list linearly showing sequence

Output

Tree:

1

  2

    4

    5

  3



Array:

[1,2,3,4,5]



Linked List:

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because we visit each node once to build or print

Space: O(n) because we store all nodes in memory

vs Alternative: Tree uses pointers to show hierarchy clearly, arrays use indexes but lose hierarchy, linked lists show order but no branching; tree is best for hierarchical data

Edge Cases

Empty tree, array, or linked list

Print functions handle empty structures gracefully without errors

DSA Rust

while let Some(node) = curr { ... } in print_linked_list handles empty list

Single node tree or list

Structure shows just one node with no children or next

DSA Rust

print_tree and print_linked_list handle single node by printing value only

When to Use This Pattern

When you see data with parent-child relationships or multiple levels, think of using a tree because it naturally models hierarchy better than arrays or linked lists.

Common Mistakes

Mistake: Using an array or linked list to represent hierarchical data and expecting to easily find parents or children
Fix: Use a tree structure with nodes that have pointers to children to represent hierarchy clearly

Summary

Shows how trees, arrays, and linked lists represent data differently when hierarchy matters

Use trees to represent data with parent-child relationships and multiple levels

Trees keep hierarchy with pointers to children, arrays keep order but no hierarchy, linked lists show sequence only

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