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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Node Count in a Simple Binary Tree

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

DSA C++

#include <iostream>

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

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

int main() {
    Node* root = new Node(10);
    root->left = new Node(20);
    root->right = new Node(30);
    root->left->left = new Node(40);
    root->left->right = new Node(50);
    int total = countNodes(root);
    std::cout << total << std::endl;
    return 0;
}

A 5

B 4

C 3

D 6

💡 Hint

Count each node including root and all children recursively.

The tree has nodes: 10 (root), 20, 30, 40, 50. Total nodes = 5.

❓ Predict Output

intermediate

Count Nodes in a Skewed Binary Tree

What will be the output of the node count function on this skewed binary tree?

DSA C++

#include <iostream>

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

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

int main() {
    Node* root = new Node(1);
    root->right = new Node(2);
    root->right->right = new Node(3);
    root->right->right->right = new Node(4);
    int total = countNodes(root);
    std::cout << total << std::endl;
    return 0;
}

A 4

B 3

C 5

D 2

💡 Hint

Count all nodes along the right side only.

The tree has nodes 1, 2, 3, 4 all on the right side. Total nodes = 4.

🧠 Conceptual

advanced

Understanding Node Counting Complexity

What is the time complexity of counting total nodes in a binary tree using a recursive approach?

A O(n^2), where n is the number of nodes

B O(log n), where n is the number of nodes

C O(n), where n is the number of nodes

D O(1), constant time

💡 Hint

Each node is visited exactly once.

The recursive function visits every node once, so time complexity is linear O(n).

🔧 Debug

advanced

Identify the Bug in Node Counting Function

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

DSA C++

#include <iostream>

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 countNodes(root);
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(7);
    int total = countNodes(root);
    std::cout << total << std::endl;
    return 0;
}

A Outputs 3

B Outputs 5

C Outputs 1

D Stack overflow due to infinite recursion

💡 Hint

Check the base case condition carefully.

Base case recurses on nullptr, causing infinite recursion and stack overflow.

🚀 Application

expert

Count Nodes in a Complete Binary Tree Using Iteration

Which iterative approach correctly counts total nodes in a binary tree without recursion?

DSA C++

#include <queue>

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

int countNodesIterative(Node* root) {
    if (!root) return 0;
    std::queue<Node*> q;
    q.push(root);
    int count = 0;
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        count++;
        // Fill in the missing code here
    }
    return count;
}

A q.push(current->left); q.push(current->right);

B if (current->left) q.push(current->left); if (current->right) q.push(current->right);

C if (current->left) q.push(current->right); if (current->right) q.push(current->left);

D if (current->left == nullptr && current->right == nullptr) break;

💡 Hint

Add children nodes to the queue only if they exist.

Option B correctly adds left and right children if they exist, ensuring all nodes are counted.