I was thinking an idea with arbitrary input for a long time, but nothing came out. Is that possible to develop a linear time and constant space solution if input can be negative??
What if input can be negative?

I doubt it. Here's a vague argument against it:
With negative numbers, you could have a path like this:
1level: ++ ++ ++       ... 0level: + ++ ++ + ...
That is, you could encode a binary string, i.e., arbitrary data, in the path. And at some point the path could go above the 1level, then somewhere left, and down to the 1level, essentially testing a certain bit. Any bit could get tested, and if you don't go through the path again, you'd have to test the bit with just the O(1) data you kept. Which would mean you'd have a way to compress arbitrary data into O(1) space, which is impossible. So if you use only O(1) space, you'd have to go through the path again.
Now imagine the 1level isn't just one unit above the 0level but many units, and the bitwidth is also wide. So that the path doing a bittest over a 0bit can go back up, move to another bit, test that one, move back up and somewhere else and test more bits, all without crossing. This way I could test many bits and you'd have go through the path many times, costing more than O(n) time.