Some fantastic solutions posted so far. Here's my attempt:

```
var countNodes = function(root) {
if (!root) return 0;
let h = depth(root);
let maxLeaves = 1 << h;
let low = 0;
let high = maxLeaves - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (depth(root, mid, h) === h) {
low = mid + 1;
} else {
high = mid;
}
}
return maxLeaves + low - (depth(root, low, h) < h);
};
function depth(root, path = 0, max = 0) {
let h = -1;
let mask = 1 << max - 1;
let node = root;
while (node) {
h++;
node = (path & mask) ? node.right : node.left;
mask >>>= 1;
}
return h;
}
```

- A complete tree has
`2 ** h - 1`

nodes plus its bottom-level nodes (`h`

is 0-indexed). - We find the number of bottom-level nodes by binary search from
`0`

to`maxLeaves - 1`

. - We can get to the leaves in order by using the binary representation of our search position as a path, where
`0`

means traverse left and`1`

means traverse right. So for a tree with`h = 4`

,`0000`

gets to the left-most leaf,`0001`

the next leaf, and so on.

Our time complexity is O(log(max leaves) * (tree height)) = O(h²) or O(log²n) in the number of nodes.