Count Total Nodes in Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of counting nodes in this binary tree?

Consider the following Rust code that counts nodes in a binary tree. What is the printed 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 count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            1 + count_nodes(node.borrow().left.clone()) + count_nodes(node.borrow().right.clone())
        }
    }
}

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

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

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

A Total nodes: 3

B Total nodes: 2

C Total nodes: 5

D Total nodes: 4

💡 Hint

Count each node starting from root, including all children.

The tree has nodes with values 1, 2, 3, and 4. Counting all nodes gives 4.

❓ Predict Output

intermediate

What is the output after adding a right child to the left node?

Given the Rust code below, what will be the output after adding a right child with value 5 to the left node?

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 {
    match root {
        None => 0,
        Some(node) => {
            1 + count_nodes(node.borrow().left.clone()) + count_nodes(node.borrow().right.clone())
        }
    }
}

fn main() {
    let root = TreeNode::new(1);
    let left = TreeNode::new(2);
    let right = TreeNode::new(3);
    let left_left = TreeNode::new(4);
    let left_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());
    left.borrow_mut().right = Some(left_right.clone());

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

A Total nodes: 5

B Total nodes: 3

C Total nodes: 6

D Total nodes: 4

💡 Hint

Count all nodes including the new right child of the left node.

The tree now has nodes 1, 2, 3, 4, and 5. Total nodes counted is 5.

🔧 Debug

advanced

What error occurs when counting nodes with this broken Rust code?

This Rust code attempts to count nodes but has a bug. What error will it cause when run?

DSA Rust

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

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 root.is_none() {
        return 0;
    }
    let node = root.unwrap();
    1 + count_nodes(node.borrow().left.clone()) + count_nodes(node.borrow().right.clone())
}

fn main() {
    let root = TreeNode::new(1);
    let left = TreeNode::new(2);
    root.borrow_mut().left = Some(left);
    let total = count_nodes(Some(root));
    println!("Total nodes: {}", total);
}

A panic: called `Option::unwrap()` on a `None` value

B Output: Total nodes: 2

C Compilation error: cannot move out of borrowed content

D Runtime error: stack overflow

💡 Hint

Check how unwrap() is used on Option inside count_nodes.

Using unwrap() on Option inside count_nodes moves the value, which is not allowed because it borrows the node. This causes a compilation error.

🧠 Conceptual

advanced

Why use Rc> for binary trees in Rust?

In Rust, why do we often use Rc> to represent nodes in a binary tree?

A To ensure nodes are immutable and owned by only one parent

B To allow multiple owners and mutable access to nodes at runtime

C To prevent any runtime borrowing errors by using unsafe code

D To optimize memory usage by avoiding reference counting

💡 Hint

Think about ownership and mutability in Rust's strict rules.

Rc allows multiple owners of the same data, and RefCell allows mutable access checked at runtime. Together they enable shared mutable trees.

🚀 Application

expert

What is the total node count after this sequence of insertions?

Starting with an empty binary tree, the following insertions happen in order: 10 (root), 5 (left child of 10), 15 (right child of 10), 3 (left child of 5), 7 (right child of 5), 12 (left child of 15). What is the total number of nodes in the tree?

A 6

B 5

C 7

D 4

💡 Hint

Count each inserted node carefully, including root and all children.

The nodes inserted are 10, 5, 15, 3, 7, and 12, totaling 6 nodes.

Practice

1. What does the function to count total nodes in a binary tree do?

easy

A. It returns the sum of all node values.

B. It returns the total number of nodes in the tree.

C. It returns the height of the tree.

D. It returns the number of leaf nodes only.

Solution

1. Step 1: Understand the function's purpose

   The function is designed to count how many nodes exist in the entire binary tree.

2. Step 2: Differentiate from other tree properties

   Counting nodes is different from calculating height, sum of values, or counting leaves.

3. Final Answer:

   It returns the total number of nodes in the tree. -> Option B

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count all nodes, not just leaves or height [OK]

Common Mistakes:

• Confusing node count with tree height
• Counting only leaf nodes
• Summing node values instead of counting

2. Which Rust code snippet correctly defines a binary tree node struct for counting nodes?

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: &Node, right: &Node }

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

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive types like binary trees require using Box and Option to allow nullable pointers and heap allocation.

2. Step 2: Identify correct struct syntax

   Option allows left and right to be either None or Some(Box<Node>), which is correct for binary trees.

3. Final Answer:

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

4. Quick Check:

   Use Option for nullable children [OK]

Hint: Use Option for child nodes in Rust [OK]

Common Mistakes:

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

3. What is the output of this Rust function call counting nodes in the given tree?

fn count_nodes(root: &Option) -> i32 {
    match root {
        None => 0,
        Some(node) => 1 + count_nodes(&node.left) + count_nodes(&node.right),
    }
}

// Tree structure:
//       10
//      /  \
//     5    15
//          /
//         12

let root = Some(Box::new(Node {
    value: 10,
    left: Some(Box::new(Node { value: 5, left: None, right: None })),
    right: Some(Box::new(Node {
        value: 15,
        left: Some(Box::new(Node { value: 12, left: None, right: None })),
        right: None,
    })),
}));

println!("{}", count_nodes(&root));

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Count nodes in each subtree

   Root node (10) counts as 1. Left subtree has 1 node (5). Right subtree has 2 nodes (15 and 12).

2. Step 2: Sum all nodes

   Total nodes = 1 (root) + 1 (left) + 2 (right) = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   1 + 1 + 2 = 4 [OK]

Hint: Add 1 for root plus counts of left and right [OK]

Common Mistakes:

• Counting only leaf nodes
• Forgetting to add root node
• Miscounting subtree nodes

4. Identify the error in this Rust function that counts nodes in a binary tree:

fn count_nodes(root: Option) -> i32 {
    if root.is_none() {
        return 0;
    }
    1 + count_nodes(root.unwrap().left) + count_nodes(root.unwrap().right)
}

medium

A. Using unwrap() twice consumes the value causing a move error.

B. The function should return usize, not i32.

C. The base case should return 1 instead of 0.

D. The function should use references instead of ownership.

Solution

1. Step 1: Understand ownership and unwrap behavior

   Calling unwrap() consumes the Option, so calling it twice on the same variable causes a move error.

2. Step 2: Identify correct fix

   Store the result of unwrap() in a variable to avoid multiple moves or use references.

3. Final Answer:

   Using unwrap() twice consumes the value causing a move error. -> Option A

4. Quick Check:

   unwrap() moves value; multiple calls cause error [OK]

Hint: Call unwrap() once, store result before use [OK]

Common Mistakes:

• Calling unwrap() multiple times on same Option
• Ignoring ownership and move semantics
• Returning wrong base case value

5. Given a binary tree where each node has a value and pointers to left and right children, how would you modify the counting function to count only nodes with values greater than 10? Choose the correct Rust function implementation.

hard

A. fn count_nodes_gt_10(root: &Option) -> i32 {
if root.is_none() {
return 0;
}
let node = root.unwrap();
if node.value > 10 {
1 + count_nodes_gt_10(&node.left) + count_nodes_gt_10(&node.right)
} else {
0
}
}

B. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => 1 + count_nodes_gt_10(&node.left) + count_nodes_gt_10(&node.right),
}
}

C. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => {
let count_left = count_nodes_gt_10(&node.left);
let count_right = count_nodes_gt_10(&node.right);
if node.value > 10 {
1 + count_left + count_right
} else {
count_left + count_right
}
}
}
}

D. fn count_nodes_gt_10(root: &Option) -> i32 {
match root {
None => 0,
Some(node) => if node.value > 10 { 1 } else { 0 },
}
}

Solution

1. Step 1: Traverse entire tree recursively

   We must visit every node to check its value and count accordingly.

2. Step 2: Count nodes with value > 10 correctly

   If node's value is greater than 10, add 1 plus counts from left and right subtrees; else add only counts from children.

3. Final Answer:

   Function that adds 1 only if node.value > 10, else sums children counts. -> Option C

4. Quick Check:

   Count nodes with value > 10 recursively [OK]

Hint: Add 1 only if node value > 10, else sum children [OK]

Common Mistakes:

• Counting all nodes regardless of value
• Returning 0 when node value <= 10 without counting children
• Not traversing entire tree