title: Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time
body: <p><strong>This is not homework, this is an interview question.</strong></p>
  
  <p>The catch here is that the algorithm should be constant space.
  I'm pretty clueless on how to do this without a stack, I'd post what I've written using a stack, but it's not relevant anyway.</p>
  
  <p>Here's what I've tried: I attempted to do a pre-order traversal and I got to the left-most node, but I'm stuck there. I don't know how to "recurse" back up without a stack/parent pointer.</p>
  
  <p>Any help would be appreciated.</p>
  
  <p>(I'm tagging it as Java since that's what I'm comfortable using, but it's pretty language agnostic as is apparent.)</p>