222. Count Complete Tree Nodes

Problem Statement

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

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.

Intuition

Approach 1: 
Traversal

Approach 2:
Nodes in complete BT is 2^n-1;

so we travel all the way to left and right
if found equal, return 2^n-1

Else we move left and right

Now the complexity of this is logn*logn

As in the worst case, We are going to logn nodes for finding l == r condition
And at all logn nodes we find height for l and r in logn time

Hence logn * logn

Links

https://leetcode.com/problems/count-complete-tree-nodes/description/

Video Links

https://www.youtube.com/watch?v=u-yWemKGWO0&ab_channel=takeUforward

Approach 1:

Brute

C++

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr)
            return 0;
            
        if(!root->left and !root->right)
            return 1;

        int l=0,r=0;
        if(root->left)
            l = countNodes(root->left);

        if(root->right)
            r = countNodes(root->right);

        return 1 + l + r;   
    }
};

Approach 2:

Optimal

C++

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr)
            return 0;

        int l=0, r=0;
        TreeNode *lptr=root, *rptr=root;

        while(lptr){
            lptr = lptr->left;
            l++;
        }
        while(rptr){
            rptr = rptr->right;
            r++;
        }

        if(l == r)
            return (1<<l)-1;

        return 1 + countNodes(root->left) + countNodes(root->right); 
    }
};

Approach 3:

C++

Approach 4:

C++