Problem Statement

Given the root of a complete binary tree, determine the total number of nodes in the tree. A complete binary tree is a binary tree in which every level is completely filled except possibly for the last level, which is filled from left to right.

Examples

Example 1:

Input:
        1
       / \
      2    3
     / \   /
    4   5 6
Output: 6

Explanation:
The tree has nodes: 1, 2, 3, 4, 5, 6
Total = 6

Example 2:

Input:
        1
       / \
      2   3
     / \  / \
    4   5 6  7
Output: 7

Explanation: The tree is fully complete, so the number of nodes is (2^h - 1) = (2^3 - 1) = 8 - 1 = 7

Example 3:

Input:
        1
       / \
      2   3
     /
    4

Output: 4

Explanation: The nodes in the tree are 1, 2, 3, and 4.
Total = 4.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A complete binary tree is one where every level is fully populated, except possibly for the last level, which is filled from left to right. To determine the total number of nodes in such a tree, a straightforward approach is to use a tree traversal method to count each node. For instance, an inorder traversal method visits nodes in the order of left subtree, current node, and right subtree. By keeping a count and incrementing it each time a node is visited, you can accurately tally the total number of nodes in the tree.

Approach:

1. Start by setting up a variable to keep track of the total number of nodes in the tree, initializing it to 0.
2. **Define a Recursive Inorder Traversal Function:**
   1. **Base Case:** If the current node is null, return immediately as this signifies that there are no more nodes to process in this path.
   2. **Recursive Case:** If the current node is not null, first recursively visit the left subtree. After returning from the left subtree, increment the counter by 1 to account for the current node. Then, proceed to recursively visit the right subtree.
3. Invoke the recursive inorder traversal function starting from the root of the binary tree. Begin with the counter set to 0.
4. After completing the traversal, return the final value of the counter, which now holds the total number of nodes in the binary tree.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to perform inorder
    // traversal and count nodes
    void inorder(TreeNode* root, int &count) {
        // Base case: If the current
        // node is NULL, return
        if (root == nullptr) {
            return;
        }

        // Increment count
        // for the current node
        count++;

        // Recursively call inorder
        // on the left subtree
        inorder(root->left, count);

        // Recursively call inorder
        // on the right subtree
        inorder(root->right, count);
    }

    // Function to count nodes in the binary tree
    int countNodes(TreeNode* root) {
        // Base case: If the root is NULL,
        // the tree is empty, return 0
        if (root == nullptr) {
            return 0;
        }

        // Initialize count variable to
        // store the number of nodes
        int count = 0;

        // Call the inorder traversal
        // function to count nodes
        inorder(root, count);

        // Return the final count of
        // nodes in the binary tree
        return count;
    }
};

int main() {
    // Create the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    Solution sol;

    // Call the countNodes function
    int totalNodes = sol.countNodes(root);

    // Print the result
    cout << "Total number of nodes in the Complete Binary Tree: "
         << totalNodes << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited exactly once, ensuring a linear time complexity.
• Space Complexity: O(N) where N is the number of nodes in the binary tree. The recursive stack may use space proportional to the number of nodes, especially in a skewed tree. For a balanced tree, the space complexity is roughly O(log N) as the maximum stack depth corresponds to the tree's height.