<p>Given the <code>root</code> of a <strong>complete</strong> binary tree, return the number of the nodes in the tree.</p>

<p>According to <strong><a href="http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees" target="_blank">Wikipedia</a></strong>, 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 <code>1</code> and <code>2<sup>h</sup></code> nodes inclusive at the last level <code>h</code>.</p>

<p>Design an algorithm that runs in less than&nbsp;<code data-stringify-type="code">O(n)</code>&nbsp;time complexity.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/14/complete.jpg" style="width: 372px; height: 302px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6]
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[0, 5 * 10<sup>4</sup>]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 5 * 10<sup>4</sup></code></li>
	<li>The tree is guaranteed to be <strong>complete</strong>.</li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
// 
        int le(TreeNode* node)
        {
            if(node==NULL) return 0;
            int lh = le(node->left);
            return 1+lh;
        }

         int re(TreeNode* node)
        {
            if(node==NULL) return 0;
            int rh = re(node->right);
            return 1+rh;
        }


   
        // ab dekh yanha pe simple sa concept aa gaya jaise ki tu void me & value me bharte jata tha ab dhyan rakh yanha pe ushi jagah pe janha pr tu sum me add kar rha tha wanha par function ko return kar dena hai bas wamha tu 1 add kar rha tha tanha 1 add ka ke function ko hi return kar do easy hai kuch questions karega to samjha aa jayega

    
    
    int countNodes(TreeNode* root) {
       if(root==NULL) return 0;
        int lh = le(root);
        int rh = re(root);
       if(lh!=rh) return 1+countNodes(root->left)+countNodes(root->right);
       else return (1<<lh)-1;

    }
};
29600