Binary Tree Node Structure in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree node?

A binary tree node is a data structure that contains a value and two links (or pointers) to its left and right child nodes. It helps build a tree where each node has up to two children.

beginner

Show the basic Rust struct for a binary tree node holding an integer value.

struct TreeNode { val: i32, left: Option, right: Option, } This struct has a value and optional left and right children wrapped in Box for heap allocation.

intermediate

Why do we use Option for child nodes in Rust?

Option allows representing either Some(child node) or None (no child). Box is used to store the child node on the heap because Rust needs to know the size of types at compile time, and recursive types like TreeNode need boxing.

beginner

What does 'left: Option' mean in a binary tree node?

It means the left child of the node can either be None (no left child) or Some(Box<TreeNode>) which points to another TreeNode stored on the heap.

beginner

How does a binary tree node structure help in building trees?

Each node holds a value and links to its children, allowing us to connect nodes in a parent-child relationship. This creates a tree shape where data can be stored and accessed hierarchically.

In Rust, what does Option represent in a binary tree node?

A A child node that may or may not exist

B A fixed-size array of child nodes

C A reference to a parent node

D A value stored in the node

Option> means the child node can be Some(Box) if it exists or None if it does not.

Why is Box used for child nodes in Rust binary trees?

A To avoid using pointers

B To store child nodes on the heap because their size is unknown at compile time

C To copy child nodes automatically

D To make child nodes immutable

Box allocates data on the heap, which is necessary for recursive types like TreeNode whose size can't be known at compile time.

What is the maximum number of children a binary tree node can have?

A 2

B 3

C 1

D Unlimited

By definition, a binary tree node has up to two children: left and right.

Which Rust keyword is used to define a binary tree node structure?

A enum

B fn

C struct

D impl

struct is used to define custom data types like a binary tree node.

What does None represent in Option?

A The node is the root

B The node has a right child

C The node has a left child

D The node does not have that child

None means the child node is missing (no left or right child).

Explain how a binary tree node is structured in Rust and why Option and Box are used.

Think about how Rust handles memory and optional values.

Describe the role of left and right fields in a binary tree node.

Consider how nodes link to each other in a tree.

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