Count Total Nodes in Binary Tree in DSA C

Mental Model

We want to find how many boxes (nodes) are in a tree by counting each one exactly once.

Analogy: Imagine a family tree where each person has children. Counting total nodes is like counting every family member in the tree.

      1
     / \
    2   3
   / \
  4   5

Dry Run Walkthrough

Input: Binary tree: 1 with children 2 and 3; 2 has children 4 and 5

Goal: Count all nodes in the tree

Step 1: Start at root node 1, count 1

1 -> count=1

Why: We begin counting from the root node

Step 2: Move to left child 2, count 1 more

1 -> 2 -> count=2

Why: Count the left child node

Step 3: Move to left child of 2, node 4, count 1 more

1 -> 2 -> 4 -> count=3

Why: Count left child of node 2

Step 4: Node 4 has no children, return count 1 for this subtree

4 -> count=1

Why: Leaf node counts as 1

Step 5: Move to right child of 2, node 5, count 1 more

1 -> 2 -> 5 -> count=4

Why: Count right child of node 2

Step 6: Node 5 has no children, return count 1 for this subtree

5 -> count=1

Why: Leaf node counts as 1

Step 7: Sum counts of left and right children of 2 plus 1 for node 2: 1+1+1=3

2 subtree count=3

Why: Total nodes under node 2

Step 8: Move to right child 3, count 1 more

1 -> 3 -> count=4

Why: Count right child of root

Step 9: Node 3 has no children, return count 1 for this subtree

3 -> count=1

Why: Leaf node counts as 1

Step 10: Sum counts of left and right children of 1 plus 1 for node 1: 3+1+1=5

Total nodes = 5

Why: Total nodes in entire tree

Result:

1 -> 2 -> 4 -> null
       -> 5 -> null
   -> 3 -> null
Total nodes = 5

Annotated Code

DSA C

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

// Define a node of the binary tree
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node with given data
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Count total nodes in binary tree recursively
int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0; // base case: no node here
    }
    // count current node plus left subtree plus right subtree
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    // Build the tree from dry run example
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    int total = countNodes(root);
    printf("Total nodes = %d\n", total);
    return 0;
}

if (root == NULL) { return 0; }

stop counting when no node exists (base case)

return 1 + countNodes(root->left) + countNodes(root->right);

count current node plus all nodes in left and right subtrees

Output

Total nodes = 5

Complexity Analysis

Time: O(n) because we visit each node exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative methods, recursion is simpler but uses stack space; iterative may use explicit stack but same O(n) time

Edge Cases

Empty tree (root is NULL)

Returns 0 nodes

DSA C

if (root == NULL) { return 0; }

Single node tree

Returns 1 node

DSA C

return 1 + countNodes(root->left) + countNodes(root->right);

When to Use This Pattern

When you need to find the size of a tree or count elements, use recursive counting because each node contributes one plus its children counts.

Common Mistakes

Mistake: Forgetting to check if the node is NULL before counting
Fix: Add base case to return 0 when node is NULL

Mistake: Counting only left or right subtree and missing the current node
Fix: Always add 1 for the current node plus counts of left and right

Summary

Counts all nodes in a binary tree by visiting each node once.

Use when you need to know how many nodes are in a tree structure.

The key insight is to count the current node plus all nodes in its left and right subtrees recursively.

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