# JavaScript O(log²n) time and O(1) space using binary search

• 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;
• 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.