Count Total Nodes in Binary Tree in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has at most two children, called left and right child.

beginner

How do you count total nodes in a binary tree?

Count 1 for the current node plus the count of nodes in the left subtree and the right subtree.

beginner

What is the base case when counting nodes recursively in a binary tree?

When the current node is null, return 0 because there are no nodes to count.

beginner

Why do we add 1 in the recursive count of nodes?

Because the current node itself counts as one node in the total count.

intermediate

What is the time complexity of counting total nodes in a binary tree?

O(n), where n is the number of nodes, because each node is visited once.

What should the function return when the current node is null?

A 0

B 1

C -1

D null

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

Which of these is the correct way to count nodes in a binary tree recursively?

A count(left) * count(right)

B count(left) - count(right)

C 1 + count(left) + count(right)

D count(left) / count(right)

We add 1 for current node plus counts from left and right subtrees.

If a binary tree has 5 nodes, how many times will the counting function be called?

A 5

B 4

C 6

D 10

Each node is visited once, so 5 calls for 5 nodes.

What is the role of recursion in counting nodes in a binary tree?

A To balance the tree

B To sort the nodes

C To delete nodes

D To visit each node and sum counts from subtrees

Recursion helps visit each node and add counts from left and right.

What will be the count of nodes for an empty binary tree?

A Undefined

B 0

C -1

D 1

An empty tree has no nodes, so count is 0.

Explain how to count total nodes in a binary tree using recursion.

Think about visiting each node and adding counts from children.

Describe the time complexity of counting nodes in a binary tree and why.

Consider how many times the function runs relative to nodes.

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