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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to count nodes recursively in a binary tree.

DSA C

int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->[1]) + countNodes(root->right);
}

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

Achild

Bright

Cleft

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using root->right instead of root->left in the first recursive call.

Using an invalid field name like root->child.

The left child of the root is accessed by root->left to count nodes in the left subtree.

2fill in blank

medium

Complete the code to count nodes recursively in a binary tree.

DSA C

int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->[1]);
}

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

Aright

Bnode

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using root->left instead of root->right in the second recursive call.

Using an invalid field name like root->child.

The right child of the root is accessed by root->right to count nodes in the right subtree.

3fill in blank

hard

Fix the error in the base case to correctly count nodes in a binary tree.

DSA C

int countNodes(struct Node* root) {
    if (root == [1]) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

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

A0

BNULL

Croot

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if root == 0 instead of root == NULL.

Checking if root == false or root == root.

The base case checks if the root pointer is NULL, meaning no node exists there.

4fill in blank

hard

Fill both blanks to complete the iterative approach to count nodes using a queue.

DSA C

int countNodesIterative(struct Node* root) {
    if (root == NULL) return 0;
    int count = 0;
    struct Queue* q = createQueue();
    enqueue(q, root);
    while (!isEmpty(q)) {
        struct Node* current = dequeue(q);
        count++;
        if (current->[1] != NULL) enqueue(q, current->[1]);
        if (current->[2] != NULL) enqueue(q, current->[2]);
    }
    return count;
}

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

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using invalid fields like parent or child.

Checking only one child and missing nodes.

We check both left and right children of the current node to enqueue them for counting.

5fill in blank

hard

Fill all three blanks to complete the recursive function that counts nodes and prints the count.

DSA C

#include <stdio.h>

int countNodes(struct Node* [1]) {
    if ([1] == NULL) return 0;
    return 1 + countNodes([1]->left) + countNodes([1]->[2]);
}

int main() {
    struct Node* root = createSampleTree();
    int total = countNodes(root);
    printf("Total nodes: %[3]d\n", total);
    return 0;
}

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

Aroot

Bright

Cd

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong parameter names like node.

Using wrong format specifier in printf.

The function parameter is root; we count right child nodes with root->right; %d is the format specifier for integers.

Practice

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

easy

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

B. Counts only leaf nodes

C. Counts only nodes with two children

D. Counts nodes only at the last level

Solution

1. Step 1: Understand the function purpose

   The function visits every node in the tree to count them all.

2. Step 2: Recognize node types counted

   It includes root, internal nodes, and leaf nodes in the count.

3. Final Answer:

   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 in the tree [OK]

Common Mistakes:

• Counting only leaf nodes
• Ignoring root node in count
• Counting only nodes with two children

2. Which of the following is the correct base case for counting nodes in a binary tree recursively in C?

easy

A. if (root->left == NULL) return 0;

B. if (root == NULL) return 1;

C. if (root == NULL) return 0;

D. if (root->right == NULL) return 1;

Solution

1. Step 1: Identify base case for recursion

   When the node is NULL, it means no node exists, so count is zero.

2. Step 2: Confirm correct return value

   Return 0 to indicate no nodes to count at this branch.

3. Final Answer:

   if (root == NULL) return 0; -> Option C

4. Quick Check:

   NULL node means zero nodes [OK]

Hint: Return 0 when node is NULL [OK]

Common Mistakes:

• Returning 1 for NULL node
• Checking only left or right child for base case
• Missing base case causing infinite recursion

3. What is the output of the following code snippet counting nodes in a binary tree?

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int countNodes(Node* root) {
  if (root == NULL) return 0;
  return 1 + countNodes(root->left) + countNodes(root->right);
}

// Tree structure:
//      10
//     /  \
//    5    15
//   /    /  \
//  3    12  20

int main() {
  Node n3 = {3, NULL, NULL};
  Node n5 = {5, &n3, NULL};
  Node n12 = {12, NULL, NULL};
  Node n20 = {20, NULL, NULL};
  Node n15 = {15, &n12, &n20};
  Node root = {10, &n5, &n15};
  printf("%d", countNodes(&root));
  return 0;
}

medium

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Count nodes in left subtree

   Left subtree nodes: 5 and 3 -> 2 nodes.

2. Step 2: Count nodes in right subtree

   Right subtree nodes: 15, 12, 20 -> 3 nodes.

3. Step 3: Add root node

   Root node 10 adds 1 more node.

4. Final Answer:

   6 -> Option B

5. Quick Check:

   2 + 3 + 1 = 6 [OK]

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

Common Mistakes:

• Counting only leaf nodes
• Forgetting to add root node
• Miscounting subtree nodes

4. Find the error in this node counting function and select the correct fix:

int countNodes(Node* root) {
  if (root == NULL) return 1;
  return countNodes(root->left) + countNodes(root->right);
}

medium

A. Both A and B are needed

B. Add +1 to the return statement to count current node

C. Change base case return to 0 instead of 1

D. No error, function is correct

Solution

1. Step 1: Check base case return value

   Returning 1 for NULL node is wrong; should return 0.

2. Step 2: Check counting current node

   Function misses counting current node; add +1 to sum of children.

3. Final Answer:

   Both A and B are needed -> Option A

4. Quick Check:

   Base case 0 + count current node 1 [OK]

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

Common Mistakes:

• Returning 1 for NULL node
• Not adding 1 for current node
• Assuming function is correct without base case

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 nodes with two children only

B. Count all nodes including leaf nodes

C. Count only leaf nodes with no children

D. Count nodes where left or right child is not NULL, skip leaf nodes

Solution

1. Step 1: Identify nodes with children

   Check if node's left or right child is not NULL to confirm it has children.

2. Step 2: Count only nodes with children

   Return 1 for nodes with children plus recursive counts; skip leaf nodes.

3. Final Answer:

   Count nodes where left or right child is not NULL, skip leaf nodes -> Option D

4. Quick Check:

   Count nodes with children only [OK]

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

Common Mistakes:

• Counting leaf nodes mistakenly
• Counting only nodes with two children
• Ignoring nodes with one child