Tree vs Array vs Linked List When Hierarchy Matters in DSA Rust - Visual Comparison

Concept Flow - Tree vs Array vs Linked List When Hierarchy Matters

Start: Need to store data with hierarchy

↓

Choose Data Structure

↓

Array

↓

Flat, fixed size

↓

No hierarchy

↓

Good for index access

↓

Limited for hierarchy

This flow shows how to decide between array, linked list, and tree when hierarchy matters.

Execution Sample

DSA Rust

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

let root = Node { value: 1, children: vec![Node { value: 2, children: vec![] }] };

This Rust code creates a simple tree with a root node and one child node.

Execution Table

Step	Operation	Nodes Created	Pointer Changes	Visual State
1	Create root node with value 1	Node(1)	root -> Node(1)	1
2	Create child node with value 2	Node(2)	child -> Node(2)	1 └─ 2
3	Add child node to root's children	Node(1), Node(2)	root.children[0] -> Node(2)	1 └─ 2
4	End of construction	Node(1), Node(2)	No changes	1 └─ 2

💡 All nodes created and linked, tree structure complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
root	None	Node(1)	Node(1)	Node(1 with child Node(2))	Node(1 with child Node(2))
child	None	None	Node(2)	Node(2)	Node(2)
root.children	Empty	Empty	Empty	[Node(2)]	[Node(2)]

Key Moments - 3 Insights

Why can't we use an array to represent hierarchy easily?

Arrays store elements in a flat sequence without links to children, so they can't represent parent-child relationships as shown in execution_table rows 1-3.

Why do we need pointers (or references) in trees?

Pointers connect nodes to their children, preserving hierarchy. Without them, nodes would be isolated, as seen in variable_tracker where root.children points to child node.

Why is a linked list not ideal for hierarchy?

Linked lists connect nodes linearly, not in parent-child form. They lack multiple children per node, unlike the tree structure shown in the visual state.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what nodes exist?

A Only Node(1)

B Node(1) and Node(2)

C No nodes yet

D Node(2) only

💡 Hint

Check 'Nodes Created' column at Step 2 in execution_table

At which step does root.children get updated to include the child node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Pointer Changes' and 'Visual State' columns in execution_table

If we used an array instead of a tree, what would be missing from the structure?

A Fixed size

B Parent-child hierarchy

C Values stored

D Index access

💡 Hint

Refer to concept_flow where arrays are noted as 'No hierarchy'

Concept Snapshot

Tree vs Array vs Linked List when hierarchy matters:
- Arrays store data flat, no parent-child links
- Linked Lists connect nodes linearly, no multiple children
- Trees use nodes with pointers to children, preserving hierarchy
- Use trees when parent-child relationships are important
- Arrays and linked lists are simpler but not suited for hierarchy

Full Transcript

This lesson compares tree, array, and linked list data structures focusing on hierarchy. Arrays store data in a flat sequence without links, so they cannot represent parent-child relationships. Linked lists connect nodes linearly, which also does not support multiple children per node. Trees use nodes with pointers to children, preserving hierarchy. The Rust example creates a root node and a child node linked as parent and child. The execution table shows step-by-step node creation and linking. Variable tracking shows how pointers update to maintain the tree structure. Key moments clarify why arrays and linked lists are not suitable for hierarchical data and why pointers are essential in trees. The visual quiz tests understanding of node creation, pointer updates, and hierarchy representation. The quick snapshot summarizes when to use each structure based on hierarchy needs.

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