Count Total Nodes in Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Node Count Function on a Small Tree

What is the output of the following C code that counts total nodes in a binary tree?

DSA C

#include <stdio.h>
#include <stdlib.h>

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);
}

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("%d\n", countNodes(root));
    return 0;
}

A 4

B 6

C 3

D 5

💡 Hint

Count all nodes including root, left subtree, and right subtree recursively.

The tree has nodes: 1 (root), 2 and 3 (children of root), and 4 and 5 (children of node 2). Total nodes = 5.

❓ Predict Output

intermediate

Count Nodes in a Tree with Only Left Children

What will be printed by this code counting nodes in a binary tree where each node has only a left child?

DSA C

#include <stdio.h>
#include <stdlib.h>

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);
}

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(20);
    root->left->left = newNode(30);
    root->left->left->left = newNode(40);
    printf("%d\n", countNodes(root));
    return 0;
}

A 5

B 4

C 3

D 1

💡 Hint

Count all nodes down the left side; no right children exist.

The tree has nodes 10, 20, 30, and 40 linked only through left children. Total nodes = 4.

❓ Predict Output

advanced

Output of Count Nodes on a Full Binary Tree

What is the output of this code counting nodes in a full binary tree of height 2?

DSA C

#include <stdio.h>
#include <stdlib.h>

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);
}

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    printf("%d\n", countNodes(root));
    return 0;
}

A 8

B 6

C 7

D 5

💡 Hint

Full binary tree of height 2 has 7 nodes.

The tree has 7 nodes: root (1), two children (2,3), and four grandchildren (4,5,6,7). Total nodes = 7.

🔧 Debug

advanced

Identify the Error in Node Counting Code

What error will this code produce when counting nodes in a binary tree?

DSA C

#include <stdio.h>
#include <stdlib.h>

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);
}

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    Node* root = NULL;
    printf("%d\n", countNodes(root->left));
    return 0;
}

A Segmentation fault (accessing left of NULL)

B 0

C Compilation error: 'root' undeclared

D Prints 1

💡 Hint

Check if root is NULL before accessing its members.

root is NULL, so accessing root->left causes a segmentation fault (runtime error).

🧠 Conceptual

expert

Number of Nodes in a Perfect Binary Tree of Height h

What is the formula for the total number of nodes in a perfect binary tree of height h (where height is number of edges from root to leaf)?

A 2^(h+1) - 1

B 2^h - 1

C 2^(h-1) - 1

D h * 2

💡 Hint

Perfect binary tree has all levels fully filled.

The total nodes in a perfect binary tree of height h is 2^(h+1) - 1.

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