Binary Tree Node Structure in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a binary tree node struct with an integer value.

DSA Rust

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

impl TreeNode {
    fn new([1]: i32) -> Self {
        TreeNode {
            val: val,
            left: None,
            right: None,
        }
    }
}

Drag options to blanks, or click blank then click option'

Aval

Bdata

Cnode_val

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using a parameter name different from the struct field without mapping it.

Forgetting to define the parameter.

The constructor parameter should be named 'val' to match the field 'val' in the struct.

2fill in blank

medium

Complete the code to create a new TreeNode with value 5.

DSA Rust

let root = TreeNode::new([1]);

Drag options to blanks, or click blank then click option'

A10

B0

C5

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Passing 0 or other values instead of 5.

Forgetting to pass any value.

We want to create a node with value 5, so pass 5 to the new function.

3fill in blank

hard

Fix the error in the code to assign a left child node to root.

DSA Rust

root.left = Some(Box::new(TreeNode::new([1])));

Drag options to blanks, or click blank then click option'

A"left"

B5

CNone

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Passing a string instead of an integer.

Assigning None instead of Some(Box::new(...)).

The left child node should be created with an integer value, here 5.

4fill in blank

hard

Fill both blanks to define a function that returns true if the node has no children.

DSA Rust

impl TreeNode {
    fn is_leaf(&self) -> bool {
        self.left == [1] && self.right == [2]
    }
}

Drag options to blanks, or click blank then click option'

ANone

BSome(Box::new(TreeNode::new(0)))

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using Some(...) instead of None.

Returning true or false directly instead of comparing.

A leaf node has no children, so both left and right should be None.

5fill in blank

hard

Fill all three blanks to define a method that sets the right child node with a given value.

DSA Rust

impl TreeNode {
    fn set_right(&mut self, [1]: i32) {
        self.right = Some(Box::new(TreeNode::new([2])));
    }

    fn get_right_val(&self) -> Option<i32> {
        self.right.as_ref().map(|node| node.[3])
    }
}

Drag options to blanks, or click blank then click option'

Aval

Bvalue

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent parameter or field names.

Accessing a non-existent field.

The parameter name and field name is 'val' to match the struct field; get_right_val returns node.val.

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