Count Total Nodes in Binary Tree in DSA C++

Mental Model

We want to find how many nodes are in a tree by visiting each node once and counting it.

Analogy: Imagine counting all the people in a family tree by visiting each person and adding one to your count.

      1
     / \
    2   3
   / \
  4   5

Dry Run Walkthrough

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

Goal: Count all nodes in the tree

Step 1: Start at root node 1, count 1

Visited: 1

Why: We begin counting from the root node

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

Visited: 1 -> 2

Why: Count nodes in left subtree

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

Visited: 1 -> 2 -> 4

Why: Count nodes in left subtree of node 2

Step 4: Node 4 has no children, return count 1

Back to node 2

Why: Leaf node counted, go back to parent

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

Visited: 1 -> 2 -> 5

Why: Count nodes in right subtree of node 2

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

Back to node 2

Why: Leaf node counted, go back to parent

Step 7: Sum counts for node 2: 1 (node 2) + 1 (node 4) + 1 (node 5) = 3

Back to root node 1

Why: Total nodes in left subtree counted

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

Visited: 1 -> 3

Why: Count nodes in right subtree

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

Back to root node 1

Why: Leaf node counted, go back to parent

Step 10: Sum counts for root 1: 1 (root) + 3 (left subtree) + 1 (right subtree) = 5

Final count = 5

Why: Total nodes in entire tree counted

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int countNodes(Node* root) {
    if (root == nullptr) return 0; // base case: no node here
    int leftCount = countNodes(root->left); // count nodes in left subtree
    int rightCount = countNodes(root->right); // count nodes in right subtree
    return 1 + leftCount + rightCount; // count current node plus children
}

int main() {
    // build tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    int total = countNodes(root);
    cout << "Total nodes = " << total << endl;
    return 0;
}

if (root == nullptr) return 0; // base case: no node here

stop counting when no node exists

int leftCount = countNodes(root->left); // count nodes in left subtree

count nodes in left subtree recursively

int rightCount = countNodes(root->right); // count nodes in right subtree

count nodes in right subtree recursively

return 1 + leftCount + rightCount; // count current node plus children

sum counts of left, right, and current node

Output

Total nodes = 5

Complexity Analysis

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

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

vs Alternative: Iterative methods may use extra memory for stacks or queues, but time remains O(n)

Edge Cases

Empty tree (root is nullptr)

Returns 0 immediately as there are no nodes

DSA C++

if (root == nullptr) return 0; // base case: no node here

Single node tree

Returns 1 as only root node exists

DSA C++

return 1 + leftCount + rightCount; // count current node plus children

When to Use This Pattern

When asked to find the total number of nodes in a tree, use a recursive count pattern visiting each node once.

Common Mistakes

Mistake: Forgetting to count the current node and only counting children
Fix: Add 1 for the current node in the return statement

Mistake: Not handling the base case of null node, causing errors
Fix: Check if node is null and return 0 immediately

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.

Remember to count the current node plus counts from left and right subtrees.