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

Start from the root, recursively count nodes in left and right subtrees, then add 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 code 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	Visual State
1	Visit root	A	-	-	-	A
2	Visit left child	B	-	-	-	A ├─B
3	Visit left child of B	D	-	-	-	A ├─B ├─D
4	Left child of D is null	null	0	-	-	A ├─B ├─D
5	Right child of D is null	null	-	0	-	A ├─B ├─D
6	Count nodes at D	D	0	0	1	A ├─B ├─D(1)
7	Visit right child of B	E	-	-	-	A ├─B ├─D(1) └─E
8	Left child of E is null	null	0	-	-	A ├─B ├─D(1) └─E
9	Right child of E is null	null	-	0	-	A ├─B ├─D(1) └─E
10	Count nodes at E	E	0	0	1	A ├─B ├─D(1) └─E(1)
11	Count nodes at B	B	1	1	3	A ├─B(3)
12	Visit right child of A	C	-	-	-	A ├─B(3) └─C
13	Left child of C is null	null	0	-	-	A ├─B(3) └─C
14	Right child of C is null	null	-	0	-	A ├─B(3) └─C
15	Count nodes at C	C	0	0	1	A ├─B(3) └─C(1)
16	Count nodes at A (root)	A	3	1	5	A(5)

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

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16
Current Node	A	D	E	B	C	A
Left Count	-	0	0	1	0	3
Right Count	-	0	0	1	0	1
Total Count	-	1	1	3	1	5

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Returning 0 at null nodes (see steps 4,5,8,9,13,14) means no nodes exist there, so they don't add to the count.

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

At each node (steps 6,10,11,15,16), the function sums left count + right count + 1 for the current node, shown in the Total Count column.

Why is the root node counted last?

The root's total count (step 16) is calculated after all recursive calls return counts from left and right subtrees, ensuring full tree is counted.

Visual Quiz - 3 Questions

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

A 2

B 3

C 1

D 4

💡 Hint

Check the Total Count column at step 11 in the execution_table.

At which step does the recursion return 0 for the left child of node C?

A Step 13

B Step 14

C Step 8

D Step 4

💡 Hint

Look for 'Left child of C is null' in the Operation column in execution_table.

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

A It would stay 3

B It would decrease by 1

C It would increase by 1

D It would double

💡 Hint

Adding a child increases subtree count by 1, affecting parent node counts (see how counts sum in execution_table).

Concept Snapshot

Count Total Nodes in Binary Tree:
- Use recursion starting at root
- Base case: null node returns 0
- Recursive case: 1 + left subtree count + right subtree count
- Returns total nodes in entire tree
- Simple and elegant tree traversal method

Full Transcript

To count total nodes in a binary tree, start at the root node. If the node is null, return 0 because there is no node to count. Otherwise, recursively count the nodes in the left subtree and the right subtree. Add these counts together and add 1 for the current node itself. This process continues until all nodes are visited. The final result is the total number of nodes in the tree. The execution table shows each step visiting nodes, counting left and right children, and summing counts. The variable tracker shows how counts accumulate. Key moments clarify why null nodes return 0 and how counts sum up. The visual quiz tests understanding of counts at specific steps and effects of adding nodes.

Practice

1. What does the function to count total nodes in a binary tree do?

easy

A. Counts only the leaf nodes

B. Counts nodes only on the left subtree

C. Counts only the root node

D. Counts all nodes including root, left, and right children

Solution

1. Step 1: Understand the node counting concept

   The function counts every node in the tree, including root and all children.

2. Step 2: Differentiate from partial counts

   Counting only leaves or root ignores other nodes, so total count includes all nodes.

3. Final Answer:

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

4. Quick Check:

   Total nodes = all nodes in tree [OK]

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

Common Mistakes:

• Counting only leaf nodes
• Ignoring root node
• Counting only one subtree

2. Which of the following is the correct C# syntax to define a binary tree node class for counting nodes?

easy

A. public class Node { public int data; public Node left, right; }

B. class Node { int data; Node left, right; void count() {} }

C. public struct Node { int data; Node left; Node right; }

D. class Node { public int data; public Node left; private Node right; }

Solution

1. Step 1: Check class and member access

   public class Node { public int data; public Node left, right; } correctly defines a public class with public members for data and child nodes.

2. Step 2: Verify syntax correctness

   class Node { int data; Node left, right; void count() {} } misses access modifiers and method is irrelevant; C uses struct which is less common; D has private right node which restricts access.

3. Final Answer:

   public class Node { public int data; public Node left, right; } -> Option A

4. Quick Check:

   Correct class with public members [OK]

Hint: Use public class with public node references [OK]

Common Mistakes:

• Missing public keyword
• Using struct instead of class
• Private child nodes blocking access

3. What is the output of the following C# code that counts nodes in a binary tree?

class Node {
  public int data;
  public Node left, right;
  public Node(int val) { data = val; left = right = null; }
}

int CountNodes(Node root) {
  if (root == null) return 0;
  return 1 + CountNodes(root.left) + CountNodes(root.right);
}

// Tree:
//     1
//    / \
//   2   3
//  / 
// 4

Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);

Console.WriteLine(CountNodes(root));

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Count nodes in the tree structure

   The tree has nodes: 1 (root), 2 (left child), 3 (right child), and 4 (left child of 2), total 4 nodes.

2. Step 2: Apply recursive count function

   CountNodes returns 1 + left subtree count + right subtree count, summing to 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Nodes counted = 4 [OK]

Hint: Add 1 for root plus counts of left and right [OK]

Common Mistakes:

• Counting only children, missing root
• Miscounting null nodes
• Adding extra nodes

4. Identify the error in this C# method to count total nodes in a binary tree:

int CountNodes(Node root) {
  if (root == null) return 1;
  return CountNodes(root.left) + CountNodes(root.right);
}

medium

A. Returns 1 for null node instead of 0

B. Does not count the current root node

C. All of the above

D. Missing addition of 1 for current node

Solution

1. Step 1: Check base case return value

   Returning 1 for null node is incorrect; it should be 0 because null means no node.

2. Step 2: Check counting logic for current node

   Function does not add 1 for the current root node, so it misses counting it.

3. Step 3: Combine errors

   Both base case and missing addition cause wrong total count.

4. Final Answer:

   All of the above -> Option C

5. Quick Check:

   Base case and counting errors combined [OK]

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

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Ignoring base case correctness

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 only leaf nodes

B. Count nodes where left or right child is not null, recursively

C. Count all nodes including leaves

D. Count nodes with both children null

Solution

1. Step 1: Define condition for counting nodes

   We want to count nodes that have at least one child, so check if left or right child is not null.

2. Step 2: Modify recursive function accordingly

   Recursively count nodes where left or right child exists, ignoring leaf nodes with no children.

3. Step 3: Implement logic

   Return 1 + counts of children if node has child; else 0 for leaf nodes.

4. Final Answer:

   Count nodes where left or right child is not null, recursively -> Option B

5. Quick Check:

   Count nodes with children only [OK]

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

Common Mistakes:

• Counting all nodes including leaves
• Counting only leaves
• Counting nodes with no children