Count Total Nodes in Binary Tree in DSA Rust - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: You are working with a simple binary tree structure that stores numbers. You want to find out how many nodes are in this tree.

🎯 Goal: Build a Rust program that creates a binary tree, then counts and prints the total number of nodes in it.

📋 What You'll Learn

Create a binary tree with exactly 3 nodes: root with value 10, left child with value 5, and right child with value 15

Add a helper function to count nodes recursively

Print the total count of nodes in the tree

💡 Why This Matters

🌍 Real World

Counting nodes in a binary tree is a basic operation useful in many applications like searching, sorting, and organizing data.

💼 Career

Understanding tree structures and recursion is important for software engineering roles that involve data structures, algorithms, and system design.

1

Create the Binary Tree Structure and Nodes

Define a struct called Node with fields value: i32, left: Option>, and right: Option>. Then create a variable called root that is a Node with value 10, left child node with value 5, and right child node with value 15.

DSA Rust

// Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Add a Function to Count Nodes

Add a function called count_nodes that takes a reference to an Option> and returns an i32. The function should return 0 if the node is None, otherwise return 1 + count_nodes(left) + count_nodes(right).

DSA Rust

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

fn count_nodes(node: &Option>) -> i32 {
    // Your code here
}

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

Hint

Use match to check if the node is None or Some.

3

Call the Count Function on the Root Node

Inside main, create a variable called total_nodes and set it to the result of calling count_nodes with a reference to Some(Box::new(root)).

DSA Rust

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

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

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: None,
        })),
    };
    // Your code here
}

Hint

Wrap root in Some(Box::new(...)) to match the function parameter type.

4

Print the Total Number of Nodes

Add a println! statement to print the text Total nodes: followed by the value of total_nodes.

DSA Rust

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

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

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node {
            value: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 15,
            left: None,
            right: None,
        })),
    };
    let total_nodes = count_nodes(&Some(Box::new(root)));
    // Your code here
}

Hint

Use println!("Total nodes: {}", total_nodes); to print the result.

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