Binary Tree Node Structure in DSA Rust

Mental Model

A binary tree node holds a value and links to up to two child nodes, left and right.

Analogy: Think of a family tree where each person can have up to two children, connecting generations.

    [Root]
    /    \
 [Left]  [Right]
   ↑       ↑
  Node    Node

Dry Run Walkthrough

Input: Create a binary tree node with value 10, left child 5, right child 15

Goal: Build a simple binary tree node with two children and show its structure

Step 1: Create root node with value 10 and no children

[10] -> left: null, right: null

Why: Start with the main node before adding children

Step 2: Create left child node with value 5

[10] -> left: [5], right: null

Why: Add left child to root node

Step 3: Create right child node with value 15

[10] -> left: [5], right: [15]

Why: Add right child to root node

Result:

[10] -> left: [5], right: [15]

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn main() {
    // Step 1: Create root node with value 10
    let root = TreeNode::new(10);

    // Step 2: Create left child node with value 5
    let left_child = TreeNode::new(5);
    root.borrow_mut().left = Some(left_child);

    // Step 3: Create right child node with value 15
    let right_child = TreeNode::new(15);
    root.borrow_mut().right = Some(right_child);

    // Print the root node structure
    println!("Root: {:?}", root);
}

let root = TreeNode::new(10);

Create root node with value 10 and no children

let left_child = TreeNode::new(5);

Create left child node with value 5

root.borrow_mut().left = Some(left_child);

Attach left child to root node

let right_child = TreeNode::new(15);

Create right child node with value 15

root.borrow_mut().right = Some(right_child);

Attach right child to root node

Output

Root: RefCell { value: TreeNode { val: 10, left: Some(RefCell { value: TreeNode { val: 5, left: None, right: None } }), right: Some(RefCell { value: TreeNode { val: 15, left: None, right: None } }) } } }

Complexity Analysis

Time: O(1) because creating and linking nodes is a constant time operation

Space: O(1) for each node created, total space depends on number of nodes

vs Alternative: Using arrays to represent trees can waste space and is less flexible than linked nodes

Edge Cases

Node with no children (leaf node)

left and right pointers are None, representing no children

DSA Rust

Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))

Node with only left child

right pointer remains None, left points to child node

DSA Rust

root.borrow_mut().left = Some(left_child);

Node with only right child

left pointer remains None, right points to child node

DSA Rust

root.borrow_mut().right = Some(right_child);

When to Use This Pattern

When you need to represent hierarchical data with up to two children per node, use the binary tree node structure to link nodes efficiently.

Common Mistakes

Mistake: Using raw pointers or references without ownership management causing memory errors
Fix: Use Rc and RefCell to manage shared ownership and mutability safely in Rust

Summary

It defines a node with a value and optional left and right child links.

Use it when building trees where each node can have up to two children.

The key is each node holds pointers to children, allowing flexible tree shapes.

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