Binary Tree Node Structure in DSA Rust - Build from Scratch

Binary Tree Node Structure

📖 Scenario: You are building a simple binary tree to organize numbers. Each spot in the tree can hold one number and can connect to two other spots: one on the left and one on the right.

🎯 Goal: Create a basic binary tree node structure in Rust that can hold a number and links to left and right child nodes.

📋 What You'll Learn

Define a struct called TreeNode with three fields: value, left, and right.

The value field should hold an i32 number.

The left and right fields should be Option> to allow for empty or existing child nodes.

💡 Why This Matters

🌍 Real World

Binary trees are used in many places like organizing data for quick search, sorting, and managing hierarchical information.

💼 Career

Understanding how to build and use binary trees is important for software development roles that involve data structures, algorithms, and system design.

1

Define the TreeNode struct

Define a public struct called TreeNode with a field value of type i32.

DSA Rust

# Define the TreeNode struct with a value field
// Your code here

Hint

Use pub struct TreeNode and add a field value: i32.

2

Add left and right child nodes

Add two public fields to TreeNode called left and right. Both should be of type Option>.

DSA Rust

pub struct TreeNode {
    pub value: i32,
    // Add left and right fields here
    // Your code here
}

Hint

Use Option> for both left and right fields.

3

Create a new TreeNode instance

Create a function called new inside an impl TreeNode block that takes an i32 parameter called value and returns a TreeNode with left and right set to None.

DSA Rust

impl TreeNode {
    // Write the new function here
    // Your code here
}

Hint

Define impl TreeNode and inside it a pub fn new(value: i32) -> Self that returns a TreeNode with left and right as None.

4

Print the root node value

Create a main function. Inside it, create a variable called root by calling TreeNode::new(10). Then print the value of root using println!.

DSA Rust

fn main() {
    // Create root node and print its value
    // Your code here
}

Hint

Use let root = TreeNode::new(10); and then println!("{}", root.value); inside main.

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