Count Total Nodes in Binary Tree in DSA Java

Mental Model

Count every box in the tree by visiting each one exactly once.

Analogy: Imagine counting all the rooms in a house by walking through every door and marking each room you enter until none are left uncounted.

      [1]
     /   \
   [2]   [3]
   /    
 [4]    

Dry Run Walkthrough

Input: Binary tree: root=1, left=2, right=3, left of 2=4

Goal: Find total number of nodes in the tree

Step 1: Start at root node 1

Visit node 1 -> count so far: 1

Why: We begin counting from the root node

Step 2: Move to left child node 2

Visit node 2 -> count so far: 2

Why: Count left subtree nodes

Step 3: Move to left child of node 2, node 4

Visit node 4 -> count so far: 3

Why: Count left subtree of node 2

Step 4: Node 4 has no children, backtrack to node 2, then to node 1

No new nodes -> count remains 3

Why: Finished left subtree, now count right subtree

Step 5: Move to right child node 3

Visit node 3 -> count so far: 4

Why: Count right subtree nodes

Step 6: Node 3 has no children, traversal complete

Total count: 4

Why: All nodes visited

Result:

1 -> 2 -> 4 -> 3 -> null
Total nodes = 4

Annotated Code

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class CountNodesBinaryTree {
    // Count nodes recursively
    public static int countNodes(Node root) {
        if (root == null) {
            return 0; // base case: no node here
        }
        // count current node + left subtree + right subtree
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    public static void main(String[] args) {
        // Build 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);

        int totalNodes = countNodes(root);
        System.out.println("Total nodes = " + totalNodes);
    }
}

if (root == null) { return 0; }

stop counting when no node exists (base case)

return 1 + countNodes(root.left) + countNodes(root.right);

count current node plus all nodes in left and right subtrees

Output

Total nodes = 4

Complexity Analysis

Time: O(n) because we visit every node exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Iterative methods also visit all nodes but may use explicit stacks; recursive is simpler here

Edge Cases

Empty tree (root is null)

Returns 0 as there are no nodes

DSA Java

if (root == null) { return 0; }

Single node tree

Returns 1 as only root exists

DSA Java

return 1 + countNodes(root.left) + countNodes(root.right);

Unbalanced tree (all nodes on one side)

Counts all nodes correctly by recursive calls

DSA Java

return 1 + countNodes(root.left) + countNodes(root.right);

When to Use This Pattern

When asked to count or sum values in a tree, use recursive traversal to visit all nodes systematically.

Common Mistakes

Mistake: Forgetting to check if the node is null before counting
Fix: Add base case to return 0 when node is null

Mistake: Counting only left or right subtree, missing the other
Fix: Add counts from both left and right subtrees plus current node

Summary

Counts all nodes in a binary tree by visiting each node once.

Use when you need the total number of nodes in any binary tree.

The key is to count current node plus counts from left and right subtrees recursively.

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