<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 heightMax(TreeNode* root) {
        return root == nullptr ? 0 : 1 + heightMax(root->left);
    }

    int heightMin(TreeNode* root) {
        return root == nullptr ? 0 : 1 + heightMin(root->right);
    }

    string toBinary(int n) {
        string r;
        while(n != 0) {
            r = (n % 2 == 0 ? "0" : "1" ) + r; 
            n /= 2;
        }
        cout << r << endl;
        return r;
    }

    int countNodes(TreeNode* root) {
        int l = heightMax(root), r = heightMin(root);
        if (l == r) {
            return pow(2, l) - 1;
        }
        // else, do binary search to find where is the "splitting point"
        int minNode = pow(2, r), maxNode = pow(2, l) - 2;
        while(maxNode > minNode) {
            int avr = ((minNode + maxNode) / 2) + 1;
            string avrBin = toBinary(avr); 
            int len = avrBin.length();
            TreeNode* curr = root;
            for (int i = 1; i < len; i++) {
                if (avrBin[i] == '0') {
                    curr = curr -> left;
                } else {
                    curr = curr -> right;
                }
            }
            if (curr == nullptr) {
                // number of nodes is small
                maxNode = avr - 1;
            } else {
                minNode = avr;
            }
        }
        return maxNode;
    }
};
29700