This should be O(log n) space


#1

This is done with O(log n) space not constant space…


#2

Actually O(1) space possible: iterative solution and traverse the level using the next pointers. The next pointers of a level is populated by its previous level.