222

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        levels = -1
        cur = root
        while cur:
            levels += 1
            cur = cur.left

        def exists(num, levels):
            path = f'{num:0{levels}b}'
            cur = root
            for step in path:
                if step == '0':
                    cur = cur.left
                else:
                    cur = cur.right
            return cur is not None

        l = 0
        r = 2 ** levels

        while r - l > 1:
            mid = l + (r - l) // 2
            if exists(mid, levels):
                l = mid
            else:
                r = mid

        return 2 ** (levels) + l