Count Total Nodes in Binary Tree in DSA C - 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

The process starts at the root, recursively counts nodes in left and right subtrees, then sums them with 1 for the current node.

Execution Sample

DSA C

int countNodes(Node* root) {
  if (root == NULL) return 0;
  return 1 + countNodes(root->left) + countNodes(root->right);
}

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

Execution Table

Step	Operation	Node Visited	Left Count	Right Count	Total Count	Visual State
1	Visit root	A	-	-	-	A / \ B C
2	Visit left child	B	-	-	-	A / \ B C
3	Visit B's left child	D	-	-	-	A / \ B C / D
4	D is leaf, left count	NULL	0	-	-	A / \ B C / D
5	D is leaf, right count	NULL	-	0	-	A / \ B C / D
6	Calculate D total	D	0	0	1	A / \ B C / D(1)
7	Visit B's right child	NULL	-	-	-	A / \ B C / D(1)
8	Calculate B total	B	1	0	2	A / \ B(2) C / D(1)
9	Visit right child	C	-	-	-	A / \ B(2) C / D(1)
10	Visit C's left child	NULL	-	-	-	A / \ B(2) C / D(1)
11	Visit C's right child	E	-	-	-	A / \ B(2) C / D(1) \ E
12	E is leaf, left count	NULL	0	-	-	A / \ B(2) C / D(1) \ E
13	E is leaf, right count	NULL	-	0	-	A / \ B(2) C / D(1) \ E
14	Calculate E total	E	0	0	1	A / \ B(2) C / D(1) \ E(1)
15	Calculate C total	C	0	1	2	A / \ B(2) C(2) / D(1) \ E(1)
16	Calculate root total	A	2	2	5	A(5) / \ B(2) C(2) / \ D(1) E(1)
17	Return total nodes	A	-	-	5	Final count: 5 nodes

💡 All nodes visited, recursion ends returning total count 5

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 14	After Step 15	After Step 16	Final
Node Visited	A	D	B	E	C	A	-
Left Count	-	0	1	0	0	2	-
Right Count	-	0	0	0	1	2	-
Total Count	-	1	2	1	2	5	5

Key Moments - 3 Insights

Why do we return 0 when the node is NULL?

Because a NULL node means no node exists there, so it contributes 0 to the count. This is shown in steps 4 and 5 where left or right child is NULL and returns 0.

Why do we add 1 in the return statement?

The 1 counts the current node itself. Steps 6, 8, 14, 15, and 16 show adding 1 to the sum of left and right counts to include the current node.

How does recursion ensure all nodes are counted?

Each call counts nodes in left and right subtrees recursively. The execution table shows visiting all nodes (A, B, C, D, E) step by step, ensuring none are missed.

Visual Quiz - 3 Questions

Look at the execution table, what is the total count after visiting node B (step 8)?

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the recursion return 0 for a NULL node?

A Step 4

B Step 3

C Step 6

D Step 10

💡 Hint

Look for steps where 'Node Visited' is NULL and 'Left Count' or 'Right Count' is 0.

If node E had a left child, how would the total count at step 14 change?

A It would remain 1

B It would decrease

C It would increase

D It would become 0

💡 Hint

Adding a child node increases the count returned by that subtree, as seen in the variable_tracker for total counts.

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- If node is NULL, return 0
- Else return 1 + count(left) + count(right)
- Counts all nodes including root
- Simple and elegant recursive solution

Full Transcript

To count total nodes in a binary tree, start at the root node. If the node is NULL, return 0 because no node exists there. Otherwise, recursively count nodes in the left subtree and right subtree. Add these counts together and add 1 for the current node. This process repeats for every node until all nodes are counted. The final result 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. Counts all nodes including root, left, and right children

B. Counts only leaf nodes

C. Counts only nodes with two children

D. Counts nodes only at the last level

Solution

1. Step 1: Understand the function purpose

   The function visits every node in the tree to count them all.

2. Step 2: Recognize node types counted

   It includes root, internal nodes, and leaf nodes in the count.

3. Final Answer:

   Counts all nodes including root, left, and right children -> Option A

4. Quick Check:

   Total nodes = all nodes in tree [OK]

Hint: Count every node visited in the tree [OK]

Common Mistakes:

• Counting only leaf nodes
• Ignoring root node in count
• Counting only nodes with two children

2. Which of the following is the correct base case for counting nodes in a binary tree recursively in C?

easy

A. if (root->left == NULL) return 0;

B. if (root == NULL) return 1;

C. if (root == NULL) return 0;

D. if (root->right == NULL) return 1;

Solution

1. Step 1: Identify base case for recursion

   When the node is NULL, it means no node exists, so count is zero.

2. Step 2: Confirm correct return value

   Return 0 to indicate no nodes to count at this branch.

3. Final Answer:

   if (root == NULL) return 0; -> Option C

4. Quick Check:

   NULL node means zero nodes [OK]

Hint: Return 0 when node is NULL [OK]

Common Mistakes:

• Returning 1 for NULL node
• Checking only left or right child for base case
• Missing base case causing infinite recursion

3. What is the output of the following code snippet counting nodes in a binary tree?

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int countNodes(Node* root) {
  if (root == NULL) return 0;
  return 1 + countNodes(root->left) + countNodes(root->right);
}

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

int main() {
  Node n3 = {3, NULL, NULL};
  Node n5 = {5, &n3, NULL};
  Node n12 = {12, NULL, NULL};
  Node n20 = {20, NULL, NULL};
  Node n15 = {15, &n12, &n20};
  Node root = {10, &n5, &n15};
  printf("%d", countNodes(&root));
  return 0;
}

medium

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Count nodes in left subtree

   Left subtree nodes: 5 and 3 -> 2 nodes.

2. Step 2: Count nodes in right subtree

   Right subtree nodes: 15, 12, 20 -> 3 nodes.

3. Step 3: Add root node

   Root node 10 adds 1 more node.

4. Final Answer:

   6 -> Option B

5. Quick Check:

   2 + 3 + 1 = 6 [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. Find the error in this node counting function and select the correct fix:

int countNodes(Node* root) {
  if (root == NULL) return 1;
  return countNodes(root->left) + countNodes(root->right);
}

medium

A. Both A and B are needed

B. Add +1 to the return statement to count current node

C. Change base case return to 0 instead of 1

D. No error, function is correct

Solution

1. Step 1: Check base case return value

   Returning 1 for NULL node is wrong; should return 0.

2. Step 2: Check counting current node

   Function misses counting current node; add +1 to sum of children.

3. Final Answer:

   Both A and B are needed -> Option A

4. Quick Check:

   Base case 0 + count current node 1 [OK]

Hint: Base case 0 + add 1 for current node [OK]

Common Mistakes:

• Returning 1 for NULL node
• Not adding 1 for current node
• Assuming function is correct without base case

5. Given a binary tree where some nodes have only one child, how would you modify the counting function to count only nodes that have at least one child?

hard

A. Count nodes with two children only

B. Count all nodes including leaf nodes

C. Count only leaf nodes with no children

D. Count nodes where left or right child is not NULL, skip leaf nodes

Solution

1. Step 1: Identify nodes with children

   Check if node's left or right child is not NULL to confirm it has children.

2. Step 2: Count only nodes with children

   Return 1 for nodes with children plus recursive counts; skip leaf nodes.

3. Final Answer:

   Count nodes where left or right child is not NULL, skip leaf nodes -> Option D

4. Quick Check:

   Count nodes with children only [OK]

Hint: Count nodes having at least one child only [OK]

Common Mistakes:

• Counting leaf nodes mistakenly
• Counting only nodes with two children
• Ignoring nodes with one child