222-1

/**
 * 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 countNodes(TreeNode* root) {
        if(!root) return 0;
        int depth = getDepth(root);
        int left = 1, right = pow(2, depth)-1, mid;
        while(left <= right){
            mid = (left+right)>>1;
            if(check(mid, depth, root))
                left = mid+1;
            else
                right = mid-1;
        }
        return pow(2, depth) - 1 + left;
    }

    int getDepth(TreeNode *root){
        int depth = 0;
        while(root->left){
            depth++;
            root = root->left;
        }
        return depth;
    }

    bool check(int idx, int depth, TreeNode *root){
        int left = 0, right = pow(2, depth)-1, mid;
        for(int i=0; i<depth; i++){
            mid = (left+right)>>1;
            if(idx <= mid){
                root = root->left;
                right = mid;
            }
            else{
                root = root->right;
                left = mid+1;
            }
        }
        return root != NULL;
    }

};