Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Rust - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes in a Binary Tree

What is the printed structure of the binary tree after inserting nodes 10, 5, 15, 3, 7 in that order?

DSA Rust

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

impl Node {
    fn new(value: i32) -> Self {
        Node { value, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val < self.value {
            match self.left {
                Some(ref mut left_node) => left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }

    fn print_in_order(&self) {
        if let Some(ref left) = self.left {
            left.print_in_order();
        }
        print!("{} -> ", self.value);
        if let Some(ref right) = self.right {
            right.print_in_order();
        }
    }
}

fn main() {
    let mut root = Node::new(10);
    root.insert(5);
    root.insert(15);
    root.insert(3);
    root.insert(7);
    root.print_in_order();
}

A 10 -> 5 -> 3 -> 7 -> 15 ->

B 3 -> 5 -> 7 -> 10 -> 15 ->

C 15 -> 10 -> 7 -> 5 -> 3 ->

D 3 -> 7 -> 5 -> 10 -> 15 ->

💡 Hint

Think about how in-order traversal prints nodes in ascending order for a binary search tree.

The insert method places smaller values to the left and larger or equal values to the right. In-order traversal visits left subtree, node, then right subtree, resulting in sorted order.

🧠 Conceptual

intermediate

Why Trees Are Better Than Arrays for Hierarchical Data

Which of the following reasons best explains why trees are used instead of arrays or linked lists for hierarchical data?

A Trees allow efficient representation of parent-child relationships with multiple branches, unlike arrays or linked lists which are linear.

B Arrays can store hierarchical data but require more memory than trees.

C Linked lists can represent hierarchical data better than trees because they use pointers.

D Trees are slower to traverse than arrays, making them better for hierarchical data.

💡 Hint

Think about how data with multiple levels and branches is structured.

Trees naturally represent hierarchical data with nodes having multiple children, which arrays and linked lists cannot do efficiently because they are linear structures.

🔧 Debug

advanced

Find the Bug in Tree Node Search Function

What error will this Rust code produce when searching for a value in a binary tree?

DSA Rust

fn search(node: &Option<Box<Node>>, val: i32) -> bool {
    if let Some(ref n) = node {
        if n.value == val {
            return true;
        } else if val < n.value {
            search(&n.left, val)
        } else {
            search(&n.right, val)
        }
    } else {
        false
    }
}

A Compilation error: mismatched types in return

B Runtime error: stack overflow due to infinite recursion

C Compilation error: missing return for else branch

D No error, returns true if value found, false otherwise

💡 Hint

Check if all code paths return a boolean value.

The function does not return false when the node is None, so the else branch is missing a return value, causing a compilation error.

🚀 Application

advanced

Choosing Data Structure for Fast Lookup and Hierarchy

You need to store a company's organizational chart with fast lookup by employee ID and hierarchical relationships. Which data structure is best?

A Hash map with employee ID keys and tree nodes as values

B Array of employees sorted by ID

C Linked list of employees in order of joining

D Binary Search Tree with employee ID as key

💡 Hint

Consider both fast lookup and hierarchical structure.

A hash map provides O(1) lookup by employee ID, and storing tree nodes as values maintains the hierarchy, combining both needs efficiently.

🧠 Conceptual

expert

Why Linked Lists and Arrays Cannot Efficiently Represent Hierarchies

Which statement best explains why linked lists and arrays are inefficient for representing hierarchical data compared to trees?

A Trees use less memory than arrays and linked lists for any data.

B Arrays use more memory than trees for hierarchical data.

C Linked lists allow multiple children per node but are slower than trees.

D Linked lists and arrays are linear structures and cannot naturally represent multiple child nodes per parent without complex indexing or pointers.

💡 Hint

Think about the shape and connections of hierarchical data.

Hierarchical data involves nodes with multiple children. Arrays and linked lists are linear and do not support multiple branches naturally, making trees the ideal structure.

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