Create a Binary Tree Manually in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

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

Consider this Rust code that manually creates a binary tree and prints its nodes in preorder (root, left, right). What will be the output?

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 preorder(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        print!("{} ", node.borrow().val);
        preorder(node.borrow().left.clone());
        preorder(node.borrow().right.clone());
    }
}

fn main() {
    let root = TreeNode::new(10);
    let left = TreeNode::new(5);
    let right = TreeNode::new(15);
    let left_left = TreeNode::new(3);

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    left.borrow_mut().left = Some(left_left.clone());

    preorder(Some(root));
}

A 3 5 10 15

B 10 15 5 3

C 10 5 3 15

D 5 3 10 15

💡 Hint

Preorder traversal prints root first, then left subtree, then right subtree.

The preorder traversal visits the root node first (10), then recursively visits the left subtree (5, then 3), then the right subtree (15). So the output is '10 5 3 15 '.

❓ Predict Output

intermediate

What is the output after inserting nodes manually in this Rust binary tree?

Given this Rust code that manually inserts nodes into a binary tree, what is the output of the inorder traversal (left, root, right)?

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 inorder(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        inorder(node.borrow().left.clone());
        print!("{} ", node.borrow().val);
        inorder(node.borrow().right.clone());
    }
}

fn main() {
    let root = TreeNode::new(20);
    let left = TreeNode::new(10);
    let right = TreeNode::new(30);
    let right_left = TreeNode::new(25);

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    right.borrow_mut().left = Some(right_left.clone());

    inorder(Some(root));
}

A 20 10 25 30

B 10 20 25 30

C 10 25 20 30

D 30 25 20 10

💡 Hint

Inorder traversal prints left subtree, then root, then right subtree.

The inorder traversal visits left subtree (10), then root (20), then right subtree (25, then 30). So the output is '10 20 25 30 '.

🔧 Debug

advanced

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

This Rust code tries to create a binary tree node but has a mistake. What error will it produce when compiled?

DSA Rust

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

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

fn main() {
    let root = TreeNode::new(1);
    root.left = Some(TreeNode::new(2));
}

A error: cannot assign to `root.left` because `root` is not mutable

B error: mismatched types, expected `Box<TreeNode>`, found `Option<Box<TreeNode>>`

C error: missing semicolon after `TreeNode::new(2)`

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

💡 Hint

Check if the variable is mutable before assigning to its fields.

The variable `root` is not declared as mutable, so trying to assign to `root.left` causes a compiler error about mutability.

❓ Predict Output

advanced

What is the output of this Rust code printing a binary tree level order?

This Rust code manually creates a binary tree and prints its nodes level by level. What is the output?

DSA Rust

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

#[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 level_order(root: Option<Rc<RefCell<TreeNode>>>) {
    if root.is_none() {
        return;
    }
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());

    while !queue.is_empty() {
        let node = queue.pop_front().unwrap();
        print!("{} ", node.borrow().val);
        if let Some(left) = node.borrow().left.clone() {
            queue.push_back(left);
        }
        if let Some(right) = node.borrow().right.clone() {
            queue.push_back(right);
        }
    }
}

fn main() {
    let root = TreeNode::new(1);
    let left = TreeNode::new(2);
    let right = TreeNode::new(3);
    let left_left = TreeNode::new(4);
    let right_right = TreeNode::new(5);

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    left.borrow_mut().left = Some(left_left.clone());
    right.borrow_mut().right = Some(right_right.clone());

    level_order(Some(root));
}

A 1 2 3 4 5

B 1 3 2 5 4

C 4 2 5 3 1

D 2 4 3 1 5

💡 Hint

Level order traversal prints nodes level by level from left to right.

The tree levels are: level 1: 1; level 2: 2, 3; level 3: 4, 5. So output is '1 2 3 4 5 '.

🧠 Conceptual

expert

How many nodes are in this manually created binary tree in Rust?

Given this Rust code manually creating a binary tree, how many nodes does the tree contain after all insertions?

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 count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(node) = root {
        1 + count_nodes(node.borrow().left.clone()) + count_nodes(node.borrow().right.clone())
    } else {
        0
    }
}

fn main() {
    let root = TreeNode::new(7);
    let n1 = TreeNode::new(3);
    let n2 = TreeNode::new(9);
    let n3 = TreeNode::new(1);
    let n4 = TreeNode::new(5);
    let n5 = TreeNode::new(8);
    let n6 = TreeNode::new(10);

    root.borrow_mut().left = Some(n1.clone());
    root.borrow_mut().right = Some(n2.clone());
    n1.borrow_mut().left = Some(n3.clone());
    n1.borrow_mut().right = Some(n4.clone());
    n2.borrow_mut().left = Some(n5.clone());
    n2.borrow_mut().right = Some(n6.clone());

    let total = count_nodes(Some(root));
    println!("{}", total);
}

A 5

B 6

C 8

D 7

💡 Hint

Count all nodes including root and all children.

The tree has root plus 6 other nodes connected as left and right children, total 7 nodes.

Practice

1. What is the main purpose of creating a binary tree manually in Rust using structs and references?

easy

A. To store data in a single linear sequence

B. To create a list of numbers in ascending order

C. To build a tree structure where each node can have up to two children

D. To perform arithmetic operations on numbers

Solution

1. Step 1: Understand binary tree structure

   A binary tree is a data structure where each node has at most two children, called left and right.

2. Step 2: Purpose of manual creation in Rust

   Manually creating a binary tree in Rust involves defining nodes and linking them with references to build this two-child structure.

3. Final Answer:

   To build a tree structure where each node can have up to two children -> Option C

4. Quick Check:

   Binary tree = nodes with up to two children [OK]

Hint: Binary tree nodes have max two children [OK]

Common Mistakes:

• Confusing binary tree with linked list
• Thinking binary tree nodes have more than two children
• Assuming binary tree stores data linearly

2. Which of the following Rust code snippets correctly defines a binary tree node struct with optional left and right children?

easy

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

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

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

D. struct Node { value: i32, left: &Node, right: &Node }

Solution

1. Step 1: Check for optional children

   Binary tree nodes may or may not have children, so left and right should be Option types.

2. Step 2: Use Box for heap allocation

   Since nodes refer to other nodes recursively, Box is needed to allocate on heap and avoid infinite size.

3. Final Answer:

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

4. Quick Check:

   Optional boxed children = correct node struct [OK]

Hint: Use Option for children in Rust [OK]

Common Mistakes:

• Using direct Node type causing infinite size error
• Not wrapping children in Option for nullable links
• Using references without lifetimes causing errors

3. Given the following Rust code that manually creates a binary tree, what will be printed by the println! statement?

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(leaf)),
        right: None,
    };
    println!("{}", root.left.as_ref().unwrap().value);
}

medium

A. 1

B. 3

C. None

D. Compilation error

Solution

1. Step 1: Understand tree structure

   The root node has value 1, with left child node value 3 and no right child.

2. Step 2: Trace the println! statement

   root.left is Some(Box<Node>) containing leaf with value 3, so unwrap().value prints 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Access left child's value = 3 [OK]

Hint: Access left child with unwrap() to get value [OK]

Common Mistakes:

• Printing root value instead of left child's
• Forgetting to unwrap Option before accessing value
• Confusing left and right children

4. The following Rust code attempts to create a binary tree node but fails to compile. What is the error and how to fix it?

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

fn main() {
    let node = Node {
        value: 5,
        left: None,
        right: None,
    };
    let root = Node {
        value: 10,
        left: Some(node),
        right: None,
    };
}

medium

A. Error: cannot move `node` into `Some` because `node` does not implement Copy; fix by wrapping node in Box::new()

B. Error: missing semicolon after node declaration; fix by adding semicolon

C. Error: left field must be a reference; fix by using &node

D. No error; code compiles successfully

Solution

1. Step 1: Identify the error cause

   left field expects Option, but Some(node) tries to move Node directly, causing type mismatch.

2. Step 2: Fix by boxing node

   Wrap node in Box::new(node) inside Some to match Option type.

3. Final Answer:

   Error: cannot move `node` into `Some` because `node` does not implement Copy; fix by wrapping node in Box::new() -> Option A

4. Quick Check:

   Box node before Some to fix type error [OK]

Hint: Wrap node in Box::new() for Option [OK]

Common Mistakes:

• Trying to use node directly without Box
• Using references without lifetimes
• Ignoring compiler type mismatch errors

5. You want to manually create a binary tree in Rust with root value 10, left child 5, and right child 15. Which code snippet correctly builds this tree and prints the right child's value?

hard

A. fn main() {
struct Node {
value: i32,
left: Option,
right: Option,
}
let left = Node { value: 5, left: None, right: None };
let right = Node { value: 15, left: None, right: None };
let root = Node {
value: 10,
left: Some(left),
right: Some(right),
};
println!("{}", root.right.as_ref().unwrap().value);
}

B. fn main() {
struct Node {
value: i32,
left: Option,
right: Option,
}
let root = Node {
value: 10,
left: Some(Node { value: 5, left: None, right: None }),
right: Some(Node { value: 15, left: None, right: None }),
};
println!("{}", root.right.unwrap().value);
}

C. fn main() {
struct Node {
value: i32,
left: Option,
right: Option,
}
let root = Node {
value: 10,
left: None,
right: None,
};
println!("{}", root.right.unwrap().value);
}

D. fn main() {
struct Node {
value: i32,
left: Option,
right: Option,
}
let left = Box::new(Node { value: 5, left: None, right: None });
let right = Box::new(Node { value: 15, left: None, right: None });
let root = Node {
value: 10,
left: Some(left),
right: Some(right),
};
println!("{}", root.right.as_ref().unwrap().value);
}

Solution

1. Step 1: Check node creation and boxing

   Children must be boxed nodes wrapped in Some to match Option type.

2. Step 2: Verify printing right child's value

   Use root.right.as_ref().unwrap().value to safely access right child's value 15.

3. Final Answer:

   Code in option D correctly creates and prints right child's value 15 -> Option D

4. Quick Check:

   Box children and unwrap Option to print value [OK]

Hint: Box children nodes and unwrap Option to access value [OK]

Common Mistakes:

• Not boxing children nodes causing type errors
• Using unwrap() directly on Option without as_ref()
• Creating nodes without children or wrong types