Count Total Nodes in Binary Tree in DSA Rust

Mental Model

We want to find how many pieces (nodes) are in the whole tree by counting each one exactly once.

Analogy: Imagine counting all the people in a family tree by visiting each person once, starting from the oldest ancestor and moving down to children.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Count all nodes in the tree starting from root 1

Step 1: Start at root node 1, count nodes in left subtree

Current node: 1
Left subtree: 2 -> 4, 5
Right subtree: 3

Why: We count left side first to include all nodes there

Step 2: At node 2, count nodes in left subtree (node 4)

Current node: 2
Left child: 4
Right child: 5

Why: We count left child of 2 to include node 4

Step 3: At node 4, no children, count as 1

Node 4 counted as 1

Why: Leaf node counts as one node

Step 4: At node 2, count nodes in right subtree (node 5)

Current node: 2
Right child: 5

Why: Count right child of 2 to include node 5

Step 5: At node 5, no children, count as 1

Node 5 counted as 1

Why: Leaf node counts as one node

Step 6: Sum counts at node 2: left (1) + right (1) + 1 (node 2 itself) = 3

Node 2 subtree count = 3

Why: Include node 2 plus its children

Step 7: At root 1, count nodes in right subtree (node 3)

Current node: 1
Right child: 3

Why: Count right child of root to include node 3

Step 8: At node 3, no children, count as 1

Node 3 counted as 1

Why: Leaf node counts as one node

Step 9: Sum counts at root 1: left subtree (3) + right subtree (1) + 1 (root) = 5

Total nodes in tree = 5

Why: Sum all nodes counted in left and right plus root

Result:

1 -> 2 -> 4 -> null
1 -> 2 -> 5 -> null
1 -> 3 -> null
Total nodes counted: 5

Annotated Code

DSA Rust

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

// Define a binary tree node
#[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 }))
    }
}

// Function to count total nodes in binary tree
fn count_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(node_rc) = root {
        let node = node_rc.borrow();
        // count left subtree nodes
        let left_count = count_nodes(node.left.clone());
        // count right subtree nodes
        let right_count = count_nodes(node.right.clone());
        // sum left + right + current node (1)
        left_count + right_count + 1
    } else {
        0 // no node here
    }
}

fn main() {
    // Build tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);

    root.borrow_mut().left = Some(node2.clone());
    root.borrow_mut().right = Some(node3.clone());
    node2.borrow_mut().left = Some(node4.clone());
    node2.borrow_mut().right = Some(node5.clone());

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

if let Some(node_rc) = root {

check if current node exists to continue counting

let left_count = count_nodes(node.left.clone());

recursively count nodes in left subtree

let right_count = count_nodes(node.right.clone());

recursively count nodes in right subtree

left_count + right_count + 1

sum counts of left, right, and current node

0 // no node here

base case: no node means count zero

Output

Total nodes in tree: 5

Complexity Analysis

Time: O(n) because we visit each node exactly once to count it

Space: O(h) where h is tree height due to recursion call stack

vs Alternative: Compared to iterative traversal, recursive counting is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is None)

Returns 0 because there are no nodes

DSA Rust

if let Some(node_rc) = root {

Single node tree

Returns 1 counting the root node only

DSA Rust

left_count + right_count + 1

Tree with only left or only right children

Counts all nodes correctly by recursive calls on existing children

DSA Rust

let left_count = count_nodes(node.left.clone());

When to Use This Pattern

When asked to find the total number of nodes in a tree, use recursive traversal to count nodes because it naturally visits every node once.

Common Mistakes

Mistake: Forgetting to add 1 for the current node in the sum
Fix: Always add 1 to the sum of left and right subtree counts to include the current node

Mistake: Not handling the None (empty) node case, causing errors
Fix: Check if node exists before accessing children, return 0 if None

Summary

Counts all nodes in a binary tree by visiting each node once.

Use when you need to know how many nodes are in a tree structure.

The key is to count left subtree, right subtree, then add one for the current node.

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