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.

Practice

1. What does the function countNodes do in a binary tree?

easy

A. Checks if the binary tree is balanced

B. Finds the height of the binary tree

C. Calculates the sum of all node values

D. Counts the total number of nodes in the binary tree

Solution

1. Step 1: Understand the function purpose

   The function countNodes is designed to traverse the binary tree and count every node it visits.

2. Step 2: Differentiate from other tree functions

   Unlike functions that find height, sum values, or check balance, this function specifically returns the total count of nodes.

3. Final Answer:

   Counts the total number of nodes in the binary tree -> Option D

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count nodes by visiting each once [OK]

Common Mistakes:

• Confusing node count with tree height
• Thinking it sums node values
• Assuming it checks tree balance

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

easy

A. if (root == nullptr) return 0;

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

C. if (root == nullptr) return -1;

D. if (root == nullptr) return root->data;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null (no node), the count should be zero because there is no node to count.

2. Step 2: Check each option

   if (root == nullptr) return 0; returns 0 for null nodes, which is correct. Other options return incorrect values for base case.

3. Final Answer:

   if (root == nullptr) return 0; -> Option A

4. Quick Check:

   Null node count = 0 [OK]

Hint: Return 0 when node is null [OK]

Common Mistakes:

• Returning 1 for null node
• Returning node data in base case
• Returning negative values

3. What is the output of the following code snippet?

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

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

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << countNodes(&n3);
  return 0;
}

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Analyze the tree structure

   Node n3 is root with left child n1 and right child n2. Both n1 and n2 have no children.

2. Step 2: Count nodes recursively

   countNodes(n3) = 1 + countNodes(n1) + countNodes(n2) = 1 + 1 + 1 = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3 nodes counted [OK]

Hint: Add 1 for current node plus children counts [OK]

Common Mistakes:

• Counting only root node
• Ignoring one child subtree
• Returning zero for non-null root

4. Find the error in this code snippet for counting nodes in a binary tree:

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

medium

A. Missing addition of 1 for current node

B. Base case returns 1 instead of 0

C. Function does not handle nullptr correctly

D. No error, code is correct

Solution

1. Step 1: Check base case correctness

   Base case returns 0 for nullptr, which is correct.

2. Step 2: Check counting logic

   The function sums counts of left and right subtrees but does not add 1 for the current node itself, missing counting the root.

3. Final Answer:

   Missing addition of 1 for current node -> Option A

4. Quick Check:

   Count must include current node [OK]

Hint: Add 1 for current node in return [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Confusing base case return value

5. Given a binary tree where each node has either 0 or 2 children, and the total number of leaf nodes is 7, what is the total number of nodes in the tree?

hard

A. 14

B. 13

C. 15

D. 16

Solution

1. Step 1: Recall property of full binary trees

   In a full binary tree (nodes have 0 or 2 children), total nodes = 2 * leaf nodes - 1.

2. Step 2: Calculate total nodes

   Given leaf nodes = 7, total nodes = 2 * 7 - 1 = 13.

3. Step 3: Verify formula and options

   Formula: total nodes = 2 * leaf nodes - 1 = 2*7 -1 = 13, which matches 13.

4. Final Answer:

   13 -> Option B

5. Quick Check:

   Full binary tree nodes = 2*leaves - 1 [OK]

Hint: Use full tree formula: nodes = 2*leaves - 1 [OK]

Common Mistakes:

• Using wrong formula for total nodes
• Confusing leaf nodes with total nodes
• Selecting option without calculation