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

↓

Add 1 (current node) + left count + right count

↓

Return total count

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

Execution Sample

DSA C++

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

This function counts all nodes in a binary tree by recursively summing nodes in left and right subtrees plus 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	-	-	-	1 / \ 2 3
3	Visit left child's left child	4	-	-	-	1 / \ 2 3 / 4
4	Left child of 4 is null	null	0	-	-	1 / \ 2 3 / 4
5	Right child of 4 is null	null	-	0	-	1 / \ 2 3 / 4
6	Count nodes at 4	4	0	0	1	1 / \ 2 3 / 4
7	Visit right child of 2	5	-	-	-	1 / \ 2 3 / \ 4 5
8	Left child of 5 is null	null	0	-	-	1 / \ 2 3 / \ 4 5
9	Right child of 5 is null	null	-	0	-	1 / \ 2 3 / \ 4 5
10	Count nodes at 5	5	0	0	1	1 / \ 2 3 / \ 4 5
11	Count nodes at 2	2	1	1	3	1 / \ 2 3 / \ 4 5
12	Visit right child	3	-	-	-	1 / \ 2 3 / \ 4 5
13	Left child of 3 is null	null	0	-	-	1 / \ 2 3 / \ 4 5
14	Right child of 3 is null	null	-	0	-	1 / \ 2 3 / \ 4 5
15	Count nodes at 3	3	0	0	1	1 / \ 2 3 / \ 4 5
16	Count nodes at root	1	3	1	5	1 / \ 2 3 / \ 4 5
17	Return total count	-	-	-	5	1 / \ 2 3 / \ 4 5

💡 All nodes visited; recursion ends when null nodes are reached returning 0.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
Current Node	1	4	4	5	2	3	1	-
Left Count	-	0	0	0	1	0	3	-
Right Count	-	-	0	0	1	0	1	-
Total Count	-	-	1	1	3	1	5	5

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 at null nodes (see Step 4 and Step 8) stops recursion and counts no nodes beyond leaf ends.

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

At each node (e.g., Step 11), the function adds 1 (current node) plus counts returned from left and right recursive calls.

Why does the total count at root equal 5?

Because it sums all nodes counted in left subtree (3), right subtree (1), plus itself (1), as shown in Step 16.

Visual Quiz - 3 Questions

Look at the execution table, what is the total count after visiting node 2 (Step 11)?

A 2

B 3

C 1

D 5

💡 Hint

Check the 'Total Count' column at Step 11 in the execution table.

At which step does the function return 0 for a null node?

A Step 6

B Step 11

C Step 4

D Step 16

💡 Hint

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

If the right subtree of node 1 had one more node, how would the total count at root (Step 16) change?

A It would increase by 1

B It would stay the same

C It would decrease by 1

D It would double

💡 Hint

Total count sums all nodes; adding one node in right subtree adds 1 to total count at root.

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
- Stops when leaf children are null

Full Transcript

This concept shows how to count all nodes in a binary tree using recursion. Starting at the root, the function visits each node, counts nodes in the left subtree, counts nodes in the right subtree, then adds 1 for the current node. When a null node is reached, it returns 0 to stop recursion. The execution table traces each step visiting nodes 1, 2, 4, 5, and 3, showing counts returned from subtrees and total counts computed. The variable tracker shows how counts accumulate. Key moments clarify why null nodes return 0, how counts add up, and why the final total is 5. The visual quiz tests understanding of counts at specific steps and effects of adding nodes. This method ensures every node is counted exactly once.

Practice

1. What does the function countNodes do in a binary tree?

easy

A. Checks if the binary tree is balanced

B. Finds the height of the binary tree

C. Calculates the sum of all node values

D. Counts the total number of nodes in the binary tree

Solution

1. Step 1: Understand the function purpose

   The function countNodes is designed to traverse the binary tree and count every node it visits.

2. Step 2: Differentiate from other tree functions

   Unlike functions that find height, sum values, or check balance, this function specifically returns the total count of nodes.

3. Final Answer:

   Counts the total number of nodes in the binary tree -> Option D

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count nodes by visiting each once [OK]

Common Mistakes:

• Confusing node count with tree height
• Thinking it sums node values
• Assuming it checks tree balance

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

easy

A. if (root == nullptr) return 0;

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

C. if (root == nullptr) return -1;

D. if (root == nullptr) return root->data;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null (no node), the count should be zero because there is no node to count.

2. Step 2: Check each option

   if (root == nullptr) return 0; returns 0 for null nodes, which is correct. Other options return incorrect values for base case.

3. Final Answer:

   if (root == nullptr) return 0; -> Option A

4. Quick Check:

   Null node count = 0 [OK]

Hint: Return 0 when node is null [OK]

Common Mistakes:

• Returning 1 for null node
• Returning node data in base case
• Returning negative values

3. What is the output of the following code snippet?

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

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

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << countNodes(&n3);
  return 0;
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Analyze the tree structure

   Node n3 is root with left child n1 and right child n2. Both n1 and n2 have no children.

2. Step 2: Count nodes recursively

   countNodes(n3) = 1 + countNodes(n1) + countNodes(n2) = 1 + 1 + 1 = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3 nodes counted [OK]

Hint: Add 1 for current node plus children counts [OK]

Common Mistakes:

• Counting only root node
• Ignoring one child subtree
• Returning zero for non-null root

4. Find the error in this code snippet for counting nodes in a binary tree:

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

medium

A. Missing addition of 1 for current node

B. Base case returns 1 instead of 0

C. Function does not handle nullptr correctly

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   Base case returns 0 for nullptr, which is correct.

2. Step 2: Check counting logic

   The function sums counts of left and right subtrees but does not add 1 for the current node itself, missing counting the root.

3. Final Answer:

   Missing addition of 1 for current node -> Option A

4. Quick Check:

   Count must include current node [OK]

Hint: Add 1 for current node in return [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Confusing base case return value

5. Given a binary tree where each node has either 0 or 2 children, and the total number of leaf nodes is 7, what is the total number of nodes in the tree?

hard

A. 14

B. 13

C. 15

D. 16

Solution

1. Step 1: Recall property of full binary trees

   In a full binary tree (nodes have 0 or 2 children), total nodes = 2 * leaf nodes - 1.

2. Step 2: Calculate total nodes

   Given leaf nodes = 7, total nodes = 2 * 7 - 1 = 13.

3. Step 3: Verify formula and options

   Formula: total nodes = 2 * leaf nodes - 1 = 2*7 -1 = 13, which matches 13.

4. Final Answer:

   13 -> Option B

5. Quick Check:

   Full binary tree nodes = 2*leaves - 1 [OK]

Hint: Use full tree formula: nodes = 2*leaves - 1 [OK]

Common Mistakes:

• Using wrong formula for total nodes
• Confusing leaf nodes with total nodes
• Selecting option without calculation