Count Total Nodes in Binary Tree in DSA C - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: You are working with a simple binary tree structure in C. Each node contains an integer value and pointers to its left and right child nodes. Your task is to count how many nodes are in the entire tree.

🎯 Goal: Build a C program that creates a binary tree with specific nodes, then counts and prints the total number of nodes in the tree.

📋 What You'll Learn

Define a struct called Node with an integer data and two pointers left and right.

Create a binary tree with exactly 3 nodes with values 10, 20, and 30 arranged as root, left child, and right child respectively.

Write a function called countNodes that takes a pointer to the root node and returns the total number of nodes in the tree.

Print the total number of nodes in the tree.

💡 Why This Matters

🌍 Real World

Counting nodes in a binary tree is a basic operation useful in many applications like file systems, expression parsing, and organizing data hierarchically.

💼 Career

Understanding binary trees and recursion is essential for software developers working with data structures, algorithms, and system design.

1

Define the Node struct and create the root node

Define a struct called Node with an integer data and two pointers left and right to Node. Then create a root node pointer called root and allocate memory for it. Set root->data to 10 and both root->left and root->right to NULL.

DSA C

#include 
#include 

// Define Node struct and create root node
// Your code here

Hint

Use typedef struct Node to define the node. Use malloc to allocate memory for the root node.

2

Add left and right child nodes

Create two new nodes called leftChild and rightChild by allocating memory. Set leftChild->data to 20 and rightChild->data to 30. Set their left and right pointers to NULL. Then link these nodes to root->left and root->right respectively.

DSA C

#include 
#include 

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;

    // Create left and right child nodes
    // Your code here

    return 0;
}

Hint

Use malloc to create the child nodes and assign their data and pointers. Then link them to the root.

3

Write the countNodes function

Write a function called countNodes that takes a pointer to a Node called root. It should return 0 if root is NULL. Otherwise, it should return 1 + countNodes(root->left) + countNodes(root->right) to count all nodes in the tree.

DSA C

#include 
#include 

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

// Write countNodes function here
// Your code here

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;

    Node* leftChild = (Node*)malloc(sizeof(Node));
    leftChild->data = 20;
    leftChild->left = NULL;
    leftChild->right = NULL;

    Node* rightChild = (Node*)malloc(sizeof(Node));
    rightChild->data = 30;
    rightChild->left = NULL;
    rightChild->right = NULL;

    root->left = leftChild;
    root->right = rightChild;

    // Your code here

    return 0;
}

Hint

Use recursion to count nodes. Base case is when root is NULL.

4

Print the total number of nodes

Call the countNodes function with root and print the returned value using printf with the format "Total nodes: %d\n".

DSA C

#include 
#include 

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

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;

    Node* leftChild = (Node*)malloc(sizeof(Node));
    leftChild->data = 20;
    leftChild->left = NULL;
    leftChild->right = NULL;

    Node* rightChild = (Node*)malloc(sizeof(Node));
    rightChild->data = 30;
    rightChild->left = NULL;
    rightChild->right = NULL;

    root->left = leftChild;
    root->right = rightChild;

    // Print total nodes
    // Your code here

    return 0;
}

Hint

Call countNodes(root) and print the result with printf.

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