Binary Tree Node Structure in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust code creating a binary tree node?

Consider the following Rust code that defines a binary tree node and creates a root node with value 10. What will be printed?

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn main() {
    let root = TreeNode {
        val: 10,
        left: None,
        right: None,
    };
    println!("{}", root.val);
}

A 0

B None

C 10

D Compilation error

💡 Hint

Look at the value assigned to the root node's val field.

The root node is created with val = 10, and printing root.val outputs 10.

❓ Predict Output

intermediate

What is the output when accessing left child of a leaf node?

Given a binary tree node with no children, what will be the output of printing the left child?

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn main() {
    let leaf = TreeNode {
        val: 5,
        left: None,
        right: None,
    };
    match leaf.left {
        Some(_) => println!("Has left child"),
        None => println!("No left child"),
    }
}

A No left child

B Has left child

C Compilation error

D Runtime panic

💡 Hint

Check the value assigned to left field in leaf node.

The left child is None, so the match arm prints 'No left child'.

🔧 Debug

advanced

What error does this Rust code produce when creating a cyclic binary tree?

This code tries to create a binary tree node whose left child points back to itself. What error occurs?

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn main() {
    let mut root = TreeNode {
        val: 1,
        left: None,
        right: None,
    };
    root.left = Some(Box::new(root));
}

A Compilation error: cannot move out of `root` because it is borrowed

B Runtime stack overflow

C Compilation error: mismatched types

D No error, compiles and runs

💡 Hint

Consider ownership rules when assigning root inside itself.

Assigning root inside root.left tries to move root while it is borrowed, causing a compile-time error.

🧠 Conceptual

advanced

How is a binary tree node typically represented in Rust?

Which of the following best describes the typical Rust struct definition for a binary tree node?

A struct TreeNode { val: i32, left: Box<TreeNode>, right: Box<TreeNode> }

B struct TreeNode { val: i32, left: TreeNode, right: TreeNode }

C struct TreeNode { val: i32, left: &TreeNode, right: &TreeNode }

D struct TreeNode { val: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>> }

💡 Hint

Consider how to represent optional children in Rust safely.

Option> allows for nullable children and heap allocation, which is typical in Rust binary trees.

🚀 Application

expert

What is the output of this Rust code printing a simple binary tree structure?

Given the code below that creates a root node with a left child, what is the printed output?

DSA Rust

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn print_tree(node: &Option<Box<TreeNode>>) {
    match node {
        Some(n) => {
            print!("{} -> ", n.val);
            print_tree(&n.left);
        }
        None => print!("null")
    }
}

fn main() {
    let left_child = TreeNode {
        val: 5,
        left: None,
        right: None,
    };
    let root = TreeNode {
        val: 10,
        left: Some(Box::new(left_child)),
        right: None,
    };
    print_tree(&Some(Box::new(root)));
}

A 10 -> null

B 10 -> 5 -> null

C 5 -> 10 -> null

D null

💡 Hint

Trace the recursive print_tree calls starting from root.

The print_tree function prints the current node's val, then recursively prints left child, ending with null.

Practice

1. What does a binary tree node typically contain in its structure?

easy

A. A value and a pointer to the next node in a list

B. Only a value without any pointers

C. Pointers to parent and sibling nodes only

D. A value and pointers to left and right child nodes

Solution

1. Step 1: Understand binary tree node components

   A binary tree node stores data and links to two children: left and right.

2. Step 2: Compare options with definition

   Only A value and pointers to left and right child nodes correctly describes a node with value and two child pointers.

3. Final Answer:

   A value and pointers to left and right child nodes -> Option D

4. Quick Check:

   Binary tree node = value + left/right pointers [OK]

Hint: Remember: binary tree nodes have two child links [OK]

Common Mistakes:

• Thinking nodes have only one child pointer
• Confusing with linked list node structure
• Assuming nodes store parent pointers by default

2. Which of the following is the correct Rust syntax to define a binary tree node struct with integer value and optional children?

easy

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

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

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

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

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive structs must use Box to allocate on heap and Option for nullable children.

2. Step 2: Analyze each option's correctness

   struct Node { value: i32, left: Option, right: Option } uses Option correctly; others miss Box or Option causing errors.

3. Final Answer:

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

4. Quick Check:

   Recursive struct needs Option [OK]

Hint: Use Option for nullable recursive children [OK]

Common Mistakes:

• Omitting Box causing infinite size error
• Using Option<Node> without Box causing compile error
• Not wrapping children in Option for nullable links

3. Given the following Rust code, what will be printed?

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

fn main() {
    let leaf = Node { value: 3, left: None, right: None };
    let root = Node {
        value: 1,
        left: Some(Box::new(Node { value: 2, left: None, right: None })),
        right: Some(Box::new(leaf)),
    };
    println!("{} {} {}", root.value, root.left.as_ref().unwrap().value, root.right.as_ref().unwrap().value);
}

medium

A. 1 2 3

B. 1 3 2

C. 3 2 1

D. Compilation error

Solution

1. Step 1: Trace node creation and values

   Root has value 1, left child value 2, right child value 3.

2. Step 2: Understand println! macro output

   Prints root.value, left child's value, right child's value in order: 1 2 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Print root, left, right values = 1 2 3 [OK]

Hint: Follow node values left to right in print [OK]

Common Mistakes:

• Mixing left and right child values
• Forgetting to unwrap Option before accessing value
• Assuming compilation error due to Box usage

4. Identify the error in this Rust binary tree node definition:

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

medium

A. left field should be Option to allow empty child

B. right field should not use Option

C. value field must be a reference type

D. Box<Node> cannot be used inside struct

Solution

1. Step 1: Check child pointer types for nullable children

   Binary tree children can be empty, so must use Option to allow None.

2. Step 2: Identify mismatch in left field

   Left uses Box<Node> without Option, so cannot be None, causing inflexible tree.

3. Final Answer:

   left field should be Option to allow empty child -> Option A

4. Quick Check:

   Nullable children need Option [OK]

Hint: Use Option for nullable children, not just Box<Node> [OK]

Common Mistakes:

• Forgetting Option for nullable children
• Thinking Box<Node> alone can be None
• Misunderstanding Box usage in structs

5. How would you modify the Rust binary tree node struct to include a parent pointer safely without causing ownership conflicts?

hard

A. Add a parent field as raw pointer *const Node without smart pointers

B. Add a parent field as Option and use Rc for children

C. Add a parent field as Option without Rc

D. Add a parent field as Box<Node> to own the parent node

Solution

1. Step 1: Understand ownership rules in Rust for trees

   Parent pointers create cycles; Rc and Weak pointers manage shared ownership safely.

2. Step 2: Choose correct pointer types for parent and children

   Children use Rc to share ownership; parent uses Weak to avoid strong cycle.

3. Final Answer:

   Add a parent field as Option and use Rc for children -> Option B

4. Quick Check:

   Use Rc for children and Weak for parent to avoid cycles [OK]

Hint: Use Weak for parent to prevent ownership cycles [OK]

Common Mistakes:

• Using Box for parent causing ownership conflicts
• Ignoring cycles leading to memory leaks
• Using raw pointers without safety guarantees