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

Why Trees Exist and What Linked Lists and Arrays Cannot Do

📖 Scenario: Imagine you are organizing a family reunion. You want to keep track of family members and their children. Using a simple list or array makes it hard to show who is whose child. A tree structure helps show these family connections clearly.

🎯 Goal: You will build a simple tree structure in Rust to represent family members and their children. You will see why trees are better than lists or arrays for this kind of data.

📋 What You'll Learn

Create a struct called FamilyMember with a name field and a children field that holds a vector of FamilyMember

Create a root family member named exactly "Grandparent"

Add two children named exactly "Parent1" and "Parent2" to the grandparent

Add one child named exactly "Child1" to "Parent1"

Print the family tree names in a simple indented format

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like file systems, organization charts, and family trees where relationships branch out.

💼 Career

Understanding trees helps in software development roles involving data organization, search algorithms, and UI components like menus.

1

Create the FamilyMember struct

Create a struct called FamilyMember with a name field of type String and a children field of type Vec<FamilyMember>.

DSA Rust

// Define the FamilyMember struct with name and children fields
// Your code here

Hint

Use struct keyword. The children field should be a vector of FamilyMember to hold multiple children.

2

Create the root family member

Create a variable called grandparent of type FamilyMember with name set to "Grandparent" and an empty children vector.

DSA Rust

struct FamilyMember {
    name: String,
    children: Vec,
}

// Create the grandparent FamilyMember with name "Grandparent" and no children
// Your code here

Hint

Use String::from("Grandparent") to set the name. Use Vec::new() for an empty children list.

3

Add children to the grandparent

Create two FamilyMember variables called parent1 and parent2 with names "Parent1" and "Parent2" and empty children vectors. Then create a new grandparent variable with the same name but with children containing parent1 and parent2.

DSA Rust

struct FamilyMember {
    name: String,
    children: Vec,
}

let grandparent = FamilyMember {
    name: String::from("Grandparent"),
    children: Vec::new(),
};

// Create parent1 and parent2 FamilyMembers with empty children
// Then create a new grandparent with children parent1 and parent2
// Your code here

Hint

Use vec![parent1, parent2] to add children to grandparent.

4

Add a child to Parent1 and print the family tree

Create a child1 FamilyMember with name "Child1" and empty children. Then create a new parent1 with the same name but with children containing child1. Then create a new grandparent with children parent1 and parent2. Finally, write a function called print_family that takes a reference to a FamilyMember and an indentation level, and prints the family tree names indented by two spaces per level. Call print_family with grandparent and indentation 0.

DSA Rust

struct FamilyMember {
    name: String,
    children: Vec,
}

let parent1 = FamilyMember {
    name: String::from("Parent1"),
    children: Vec::new(),
};

let parent2 = FamilyMember {
    name: String::from("Parent2"),
    children: Vec::new(),
};

let grandparent = FamilyMember {
    name: String::from("Grandparent"),
    children: vec![parent1, parent2],
};

// Create child1, update parent1 with child1, update grandparent with new parent1 and parent2
// Write print_family function to print names with indentation
// Call print_family with grandparent and 0
// Your code here

Hint

Use recursion to print each member's name with indentation. Increase indentation by 1 for children. Use two spaces per indentation level.

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