Count Total Nodes in Binary Tree in DSA Java - 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 + right counts

↓

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 Java

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 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	A	Pending	Pending	Pending	A / \ B C
2	Visit left child	B	Pending	Pending	Pending	B / \ D E
3	Visit left-left child	D	0	0	1	D (leaf)
4	Visit left-right child	E	0	0	1	E (leaf)
5	Calculate left subtree count at B	B	1	1	3	Subtree rooted at B
6	Visit right child	C	Pending	Pending	Pending	C / \ F null
7	Visit right-left child	F	0	0	1	F (leaf)
8	Visit right-right child	null	0	0	0	null (empty)
9	Calculate right subtree count at C	C	1	0	2	Subtree rooted at C
10	Calculate total count at root A	A	3	2	6	Full tree counted
11	Return total count	A	3	2	6	Final count: 6 nodes

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

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	After Step 9	Final
Current Node	A	D	E	B	F	C	A
Left Count	Pending	0	0	1	Pending	1	3
Right Count	Pending	Pending	Pending	1	0	0	2
Total Count	Pending	1	1	3	1	2	6

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 execution_table rows 3, 4, and 8 where null children return 0.

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

It recursively calls itself on left and right children, sums their counts, then adds 1 for the current node. See execution_table rows 5, 9, and 10 where left and right counts are combined.

Why is the total count at the root the sum of left and right subtree counts plus one?

Because the root itself is a node, so total nodes = nodes in left subtree + nodes in right subtree + 1 (for root). This is clear in execution_table row 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total count after visiting node B (step 5)?

A 3

B 1

C 2

D 4

💡 Hint

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

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

A Step 10

B Step 3

C Step 8

D Step 11

💡 Hint

Look for 'null' nodes in the 'Node Visited' column and see their counts.

If the tree had one more leaf under node C's right child, how would the total count at root change?

A It would decrease by 1

B It would increase by 1

C It would stay the same

D It would double

💡 Hint

Total count sums all nodes; adding a leaf adds one more node.

Concept Snapshot

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

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 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. It counts all nodes including root, left, and right children.

B. It counts only the leaf nodes of the tree.

C. It counts only the nodes on the left subtree.

D. It counts only the nodes on the right subtree.

Solution

1. Step 1: Understand the node counting function

   The function visits every node in the tree, including root, left, and right children.

2. Step 2: Summarize the counting process

   It adds 1 for the current node plus counts from left and right subtrees recursively.

3. Final Answer:

   It 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 including root and children [OK]

Common Mistakes:

• Counting only leaf nodes
• Ignoring one subtree
• Counting nodes twice

2. Which of the following is the correct Java method signature to count total nodes in a binary tree?

easy

A. public int countNodes(TreeNode root)

B. int countNodes()

C. void countNodes(TreeNode root)

D. public static void countNodes(TreeNode root)

Solution

1. Step 1: Identify method return type and parameters

   The method should return an integer count and accept the root node as parameter.

2. Step 2: Match correct Java syntax

   public int countNodes(TreeNode root) correctly declares public int countNodes(TreeNode root) which returns count.

3. Final Answer:

   public int countNodes(TreeNode root) -> Option A

4. Quick Check:

   Method returns int and takes root node [OK]

Hint: Method returns int and takes root node parameter [OK]

Common Mistakes:

• Using void return type
• Missing root parameter
• Incorrect access modifier

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

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int val) { this.val = val; }
}

public class Main {
  public static int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    System.out.println(countNodes(root));
  }
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Count nodes in the tree structure

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

2. Step 2: Apply recursive countNodes function

   Function returns 1 + count of left subtree + count of right subtree = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Nodes counted = 4 [OK]

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

Common Mistakes:

• Forgetting to count root node
• Miscounting null children
• Confusing node values with count

4. Find the error in this code to count total nodes in a binary tree:

public int countNodes(TreeNode root) {
  if (root == null) {
    return 1;
  }
  return 1 + countNodes(root.left) + countNodes(root.right);
}

medium

A. Does not count the current node

B. Missing base case for leaf nodes

C. Returns 1 when root is null instead of 0

D. Uses wrong method signature

Solution

1. Step 1: Check base case for null node

   Function returns 1 when root is null, which is incorrect; it should return 0.

2. Step 2: Verify counting logic

   The counting logic correctly adds 1 for the current node and recurses to both subtrees.

3. Final Answer:

   Returns 1 when root is null instead of 0 -> Option C

4. Quick Check:

   Base case must return 0 for null [OK]

Hint: Base case for null must return 0 nodes [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Incorrect recursion calls

5. Given a binary tree where each node has either 0 or 2 children, and the total nodes count is 15, how many leaf nodes does the tree have?

hard

A. 7

B. 15

C. 16

D. 8

Solution

1. Step 1: Use property of full binary tree

   In a full binary tree, number of leaf nodes = number of internal nodes + 1.

2. Step 2: Calculate leaf nodes from total nodes

   Total nodes = leaf nodes + internal nodes = 15. So leaf nodes = internal nodes + 1. Let internal nodes = x, then x + (x + 1) = 15 -> 2x + 1 = 15 -> 2x = 14 -> x = 7. Leaf nodes = 7 + 1 = 8.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Leaf nodes = internal nodes + 1 = 8 [OK]

Hint: In full binary tree, leaves = internal nodes + 1 [OK]

Common Mistakes:

• Confusing total nodes with leaf nodes
• Forgetting full binary tree property
• Incorrect algebra for leaf count