LC #222: Count Complete Tree Nodes, but in only O(1) Space!

Absolute banger of a question. No wonder it was Google's favourite last year, and now every other Big Tech companies' favourite.

???? Challenge : Do in O(1) space

???? Requirement:?We need to find last index that is present in the last row, as it Complete Tree

???? Intuition :?

• ??We can find [low, high] range of last row by calculating depth and taking power of 2?
• ?? Then Binary Search for this last element in the last row

? Now how do we find if particular index in [low, high] present in last row or not?

• ?? Binary Search again of course!?

? But how do you decide the left or right direction while traversing Tree?

• ???Calculate the mid, if target index is in left half go left, else if target index in right half go right?

?? Basically it is Binary Search inside another Binary Search !

?? MIND = BLOWN.