Count Total Nodes in Binary Tree in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the total number of nodes in the binary tree.

DSA Java

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

Drag options to blanks, or click blank then click option'

Anull

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 1 instead of 0 for null nodes.

Returning null which causes errors.

When the node is null, it means no node exists, so return 0.

2fill in blank

medium

Complete the code to count nodes by recursively adding left and right subtree counts.

DSA Java

return 1 + countNodes([1]) + countNodes(root.right);

Drag options to blanks, or click blank then click option'

Aroot.left

Broot

Croot.right

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using root instead of root.left causes infinite recursion.

Using null causes errors.

We add the count of nodes in the left subtree by calling countNodes on root.left.

3fill in blank

hard

Fix the error in the recursive call to count the right subtree nodes.

DSA Java

return 1 + countNodes(root.left) + countNodes([1]);

Drag options to blanks, or click blank then click option'

Aroot

Broot.right

Cnull

Droot.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using root or root.left instead of root.right.

Using null causing errors.

We must call countNodes on root.right to count nodes in the right subtree.

4fill in blank

hard

Fill both blanks to complete the base case and recursive calls for counting nodes.

DSA Java

if ([1] == null) {
    return [2];
}

Drag options to blanks, or click blank then click option'

Aroot

B0

C1

Droot.left

Attempts:

3 left

💡 Hint

Common Mistakes

Checking root.left instead of root.

Returning 1 instead of 0 for null nodes.

Check if root is null, then return 0 because no nodes exist there.

5fill in blank

hard

Fill all three blanks to complete the recursive function counting total nodes.

DSA Java

public int countNodes(TreeNode [1]) {
    if ([2] == null) {
        return 0;
    }
    return 1 + countNodes([3]) + countNodes([1].right);
}

Drag options to blanks, or click blank then click option'

Aroot

Broot.left

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Checking null on wrong variable.

The function parameter is named root. We check if root is null, then recursively count nodes in root.left and root.right.

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