> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/trees/binary-tree/hard/222.-count-complete-tree-nodes.md).

# 222. Count Complete Tree Nodes

## Problem Statement

<br>

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

According to [**Wikipedia**](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees), 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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/14/complete.jpg)

<pre><code><strong>Input: root = [1,2,3,4,5,6]
</strong><strong>Output: 6
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: root = []
</strong><strong>Output: 0
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: root = [1]
</strong><strong>Output: 1
</strong></code></pre>

&#x20;

**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
```

{% code title="C++" lineNumbers="true" %}

```cpp
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;   
    }
};
```

{% endcode %}

### Approach 2:

```
Optimal
```

{% code title="C++" lineNumbers="true" %}

```cpp
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); 
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###