/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool idx_exist (int idx , TreeNode * root, int d)
    {
        int l = 1, r = pow (2,d);
        bool res = true;
        for (int i = 0 ; i < d; i ++)
        {
            int mid = l + (r - l) / 2;

            if (idx <= mid)
            {
                root = root -> left;
                r = mid - 1;
            }
            else
            {
                root = root -> right;
                l = mid + 1;
            }
        }
        if (root == nullptr)
            res = false;
        return res;
    }
    int find_depth (TreeNode* root)
    {
        int d = 0;

        while (root -> left)
        {
            d++;
            root = root -> left;
        }

        return d;
    }
public:
    int countNodes(TreeNode* root) {

        if (root == nullptr)
            return 0;

        int depth = 0 ;
        depth = find_depth (root);

        if (depth == 0)
            return 1;

        int last_level = 0, l = 1, r = pow (2, depth);
        int mid ;
        int res;
        while (l <= r)
        {
            mid = l + (r - l) / 2;

            if (idx_exist (mid , root , depth))
            {
                res = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }

        }

        return res + ( (int)  pow (2, depth) - 1);
    }
};