title: O(n) time non-recursive procedure to traverse a binary tree
body: <p>I'm reading a book called "<strong>Introduction to algorithms</strong>". I think many of you know it. I just bumped into a question which seems rather difficult:</p>
  
  <blockquote>
    <p>Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
    prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.</p>
  </blockquote>
  
  <p>I saw that there is another question like this: <a href="https://stackoverflow.com/questions/718650/how-to-traverse-a-binary-tree-in-on-time-without-extra-memory">How to traverse a binary tree in O(n) time without extra memory</a> but the main difference is that I can't modify the tree. I was thinking of using some visited flag but I haven't distilled a right solution yet. It's maybe something obvious I don't see. How would you devise an algirithm which solves this problem? Even some pointers to the answer would be appreciated.</p>