Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Rust - Why It Works

Concept Flow - Why Trees Exist and What Linked Lists and Arrays Cannot Do

Start: Need to organize data

↓

Try Array: Fast access by index

↓

Problem: Inflexible size, no hierarchy

↓

Try Linked List: Flexible size

↓

Problem: Slow search, no hierarchy

↓

Need structure for hierarchy & fast search

↓

Use Tree: Nodes with children

↓

Supports hierarchy, fast search, flexible size

↓

End: Trees solve array & list limits

Shows why arrays and linked lists fall short for hierarchical data and how trees solve these problems.

Execution Sample

DSA Rust

let array = [10, 20, 30];
// linked list representation is conceptual, not valid Rust syntax
// let linked_list = 10 -> 20 -> 30;
// Need to represent family tree
// Use tree nodes with children

Shows simple array and linked list, then the need for tree to represent hierarchy.

Execution Table

Step	Operation	Data Structure	Limitation Found	Visual State
1	Create array with 3 elements	Array: [10, 20, 30]	Fixed size, no hierarchy	[10] -> [20] -> [30]
2	Create linked list with 3 nodes	Linked List: 10 -> 20 -> 30 -> null	Slow search, no hierarchy	10 -> 20 -> 30 -> null
3	Try to represent family hierarchy	Array or Linked List	Cannot represent parent-child easily	No clear hierarchy
4	Create tree node with children	Tree: 10 / \ 20 30	Supports hierarchy and flexible size	10 ├─ 20 └─ 30
5	Add child to node 20	Tree: 10 / \ 20 30 / 40	Flexible, hierarchical	10 ├─ 20 │ └─ 40 └─ 30
6	End	Tree solves array & list limits	Hierarchical data represented	10 ├─ 20 │ └─ 40 └─ 30

💡 Trees allow hierarchy and flexible size, unlike arrays and linked lists.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	Final
Array	empty	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]
Linked List Head	null	null	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null
Tree Root	null	null	null	10 with children 20 and 30	10 with children 20 (child 40) and 30	10 with children 20 (child 40) and 30

Key Moments - 3 Insights

Why can't arrays represent hierarchical data well?

Arrays store elements in a flat sequence with fixed size, so they cannot show parent-child relationships as seen in the execution_table rows 1 and 3.

Why is linked list slow for searching compared to trees?

Linked lists require checking each node one by one (see step 2), while trees allow branching to children, reducing search time (step 4).

How do trees solve the size flexibility problem?

Trees grow by adding child nodes dynamically (step 5), unlike arrays which have fixed size (step 1).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the tree?

A 10 ├─ 20 └─ 30

B 10 -> 20 -> 30 -> null

C [10, 20, 30]

D No clear hierarchy

💡 Hint

Check the Visual State column at step 4 in execution_table.

At which step does the data structure first show hierarchy?

A Step 3

B Step 4

C Step 2

D Step 1

💡 Hint

Look for when the Visual State shows parent-child nodes in execution_table.

If we add another child to node 30, which step's visual state would it resemble?

A Step 1

B Step 4

C Step 6

D Step 5

💡 Hint

Step 6 shows tree with multiple children, similar to adding child to node 30.

Concept Snapshot

Arrays store data in fixed-size flat lists.
Linked lists allow flexible size but no hierarchy.
Trees organize data in parent-child nodes.
Trees support hierarchy and fast search.
Trees grow dynamically with children nodes.
Trees solve array and list limitations.

Full Transcript

This concept explains why trees exist by comparing them to arrays and linked lists. Arrays store data in fixed-size sequences without hierarchy, making them unsuitable for parent-child relationships. Linked lists allow flexible size but are slow for searching and also lack hierarchy. Trees organize data in nodes with children, supporting hierarchical relationships and flexible size. The execution steps show arrays and linked lists failing to represent hierarchy, while trees easily represent parent-child connections and grow dynamically. This makes trees essential for hierarchical data and faster search operations.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees always have faster access time than arrays

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data linearly, which makes representing hierarchical relationships difficult and inefficient.

2. Step 2: Identify the advantage of trees

   Trees naturally represent hierarchical data with parent-child relationships, enabling efficient searching and organization of such data.

3. Final Answer:

   Trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide -> Option A

4. Quick Check:

   Hierarchical data needs trees [OK]

Hint: Trees represent hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are simpler to implement
• Believing trees always have faster access than arrays

2. Which of the following is the correct way to define a simple binary tree node struct in Rust?

easy

A. struct Node { value: i32, left: Option, right: Option }

B. struct Node { value: i32, left: Node, right: Node }

C. struct Node { value: i32, left: &Node, right: &Node }

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

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive types like trees need indirection (Box) and optional to allow empty children.

2. Step 2: Check each option

   struct Node { value: i32, left: Option, right: Option } uses Option for left and right, which is correct. struct Node { value: i32, left: Node, right: Node } is invalid because it causes infinite size. struct Node { value: i32, left: &Node, right: &Node } uses references without lifetimes. struct Node { value: i32, left: Box<Node>, right: Box<Node> } lacks Option, so no empty child allowed.

3. Final Answer:

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

4. Quick Check:

   Recursive structs need Option [OK]

Hint: Use Option for recursive tree nodes in Rust [OK]

Common Mistakes:

• Defining child nodes without Box causing infinite size
• Using references without lifetimes
• Not using Option for nullable children

3. What will be the output of the following Rust code that builds a simple binary tree and prints the root value?

struct Node {
    value: i32,
    left: Option,
    right: Option,
}

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node { value: 5, left: None, right: None })),
        right: Some(Box::new(Node { value: 15, left: None, right: None })),
    };
    println!("{}", root.value);
}

medium

A. 15

B. 5

C. 10

D. Compilation error

Solution

1. Step 1: Analyze the tree construction

   The root node is created with value 10, left child 5, right child 15.

2. Step 2: Check the printed value

   The code prints root.value, which is 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Print root.value = 10 [OK]

Hint: Print root.value to get 10 [OK]

Common Mistakes:

• Confusing child values with root value
• Expecting print of left or right child
• Assuming compilation error due to Option usage

4. The following Rust code tries to create a binary tree node but fails to compile. What is the error?

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

fn main() {
    let root = Node {
        value: 1,
        left: Box::new(Node { value: 2, left: Box::new(Node { value: 3, left: None, right: None }), right: None }),
        right: Box::new(Node { value: 4, left: None, right: None }),
    };
}

medium

A. Cannot use None for Box<Node> fields; should use Option

B. Missing semicolon after struct definition

C. Box cannot be used inside structs

D. Cannot create nested structs in Rust

Solution

1. Step 1: Identify the field types and assigned values

   The struct fields left and right are Box<Node>, but code assigns None to some of them.

2. Step 2: Understand why None is invalid here

   None is an Option variant, but fields are Box<Node> (non-optional), so None cannot be assigned.

3. Final Answer:

   Cannot use None for Box<Node> fields; should use Option -> Option B

4. Quick Check:

   Use Option for nullable children [OK]

Hint: Use Option to allow None children [OK]

Common Mistakes:

• Thinking Box<Node> can be None
• Ignoring Option wrapper for nullable fields
• Assuming Box is not allowed in structs

5. Given that arrays and linked lists store data linearly, which of the following real-world problems is best solved using a tree data structure instead?

medium

A. Storing a list of daily temperatures in order

B. Maintaining a queue of customers waiting in line

C. Storing a sequence of characters in a string

D. Representing a company's organizational chart with managers and employees

Solution

1. Step 1: Analyze each problem type

   Options A, B, and D represent linear data best suited for arrays or linked lists.

2. Step 2: Identify hierarchical data

   Representing a company's organizational chart with managers and employees describes an organizational chart, which is hierarchical and fits tree structures.

3. Final Answer:

   Representing a company's organizational chart with managers and employees -> Option D

4. Quick Check:

   Hierarchical data needs trees [OK]

Hint: Use trees for hierarchical data like org charts [OK]

Common Mistakes:

• Choosing linear data problems for trees
• Confusing queues or sequences with trees
• Ignoring data relationships