Count Total Nodes in Binary Tree in DSA Rust - Execution Trace

Concept Flow - Count Total Nodes in Binary Tree

Start at root node

↓

Is node null?

Yes→Return 0

No↓

Count left subtree nodes

↓

Count right subtree nodes

↓

Sum left + right + 1 (current node)

↓

Return total count

Start from the root, recursively count nodes in left and right subtrees, then add 1 for the current node.

Execution Sample

DSA Rust

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

This function counts all nodes in a binary tree by recursively summing counts from left and right children plus one for the current node.

Execution Table

Step	Operation	Node Visited	Left Count	Right Count	Total Count	Tree State
1	Visit root	1	-	-	-	1 / \ 2 3
2	Visit left child	2	-	-	-	2 / \ 4 5
3	Visit left-left child	4	-	-	1	4 (leaf)
4	Visit left-right child	5	-	-	1	5 (leaf)
5	Calculate left subtree count	2	1	1	3	Subtree rooted at 2
6	Visit right child	3	-	-	-	3 / \ 6 7
7	Visit right-left child	6	-	-	1	6 (leaf)
8	Visit right-right child	7	-	-	1	7 (leaf)
9	Calculate right subtree count	3	1	1	3	Subtree rooted at 3
10	Calculate total nodes	1	3	3	7	Full tree

💡 All nodes visited; total count is sum of left + right + 1 at root.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	Final
Current Node	1 (root)	4 (left-left)	5 (left-right)	2 (left)	6 (right-left)	7 (right-right)	3 (right)	1 (root)
Left Count	N/A	N/A	N/A	1	N/A	N/A	1	3
Right Count	N/A	N/A	N/A	1	N/A	N/A	1	3
Total Count	N/A	1	1	3	1	1	3	7

Key Moments - 3 Insights

Why do we return 0 when the node is None?

Because a None node means no node exists there, so it contributes zero to the count. This is shown in execution_table step 1 where visiting a null child returns 0.

How does the function add counts from left and right subtrees?

It recursively calls itself on left and right children, then adds their counts plus 1 for the current node. See steps 5 and 9 in execution_table where left and right counts are summed.

Why do leaf nodes return 1?

Leaf nodes have no children, so left and right counts are zero, and adding 1 for the leaf itself results in 1. This is shown in steps 3, 4, 7, and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the total count for the subtree rooted at node 2?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Total Count' column at step 5 in execution_table.

At which step does the function visit the right-right child node?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look at the 'Node Visited' column in execution_table for the right-right child.

If the tree had no right subtree, how would the total count at the root change?

A It would be 0

B It would be right subtree count + 1

C It would be left subtree count + 1

D It would be unchanged

💡 Hint

Refer to the formula in the concept_flow and execution_table step 10.

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is None, return 0
- Else return 1 + count(left) + count(right)
- Sum counts from left and right subtrees plus current node
- Total nodes = size of entire tree

Full Transcript

To count total nodes in a binary tree, start at the root node. If the node is null, return zero because no node exists there. Otherwise, recursively count nodes in the left subtree and right subtree. Add these counts together and add one for the current node itself. This process repeats until all nodes are visited. The final sum is the total number of nodes in the tree.

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