Count Complete Tree Nodes - Leetcode Solution

Problem Statement: Given the root of a complete binary tree, return the number of the nodes in the tree.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Example: Input: root = [1,2,3,4,5,6] Output: 6

Input: root = [] Output: 0

Approach: Since given is a complete binary tree, it is ensured all nodes except the last level are populated completely. We can find the count of nodes from the leftmost path and rightmost path of the tree. We can compare the depth of the leftmost and rightmost node. If both nodes are at the same depth, then the number of nodes in the tree can be calculated as 2^height - 1 else we can recursively apply the same approach to the left and right subtrees.

Algorithm:

1. If root is null, return 0
2. We will check the depth of the leftmost and rightmost nodes by traversing the tree.
3. If both nodes are at the same depth, the number of nodes can be calculated as 2^height - 1
4. Else, recursively apply the same approach to the left and right subtrees.
5. Return the sum of all the nodes calculated.

Code:

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==NULL)
            return 0;
        
        int leftHeight = findLeftHeight(root);
        int rightHeight = findRightHeight(root);
        
        if(leftHeight == rightHeight)
            return pow(2,leftHeight)-1;
        
        return 1+countNodes(root->left)+countNodes(root->right);
    }
    
    int findLeftHeight(TreeNode* root)
    {
        if(root==NULL)
            return 0;
        int height = 0;
        while(root!=NULL)
        {
            height++;
            root=root->left;
        }
        return height; 
    }
    
    int findRightHeight(TreeNode* root)
    {
        if(root==NULL)
            return 0;
        int height = 0;
        while(root!=NULL)
        {
            height++;
            root=root->right;
        }
        return height; 
    }
};

1