Morris Traversal — O(1) Space Tree Walk

void morrisInorder(Node root) {
  Node cur = root;
  while (cur != null) {
    if (cur.left == null) {
      visit(cur);
      cur = cur.right;
    } else {
      Node pred = cur.left;
      while (pred.right != null && pred.right != cur) pred = pred.right;
      if (pred.right == null) {
        pred.right = cur;  // thread
        cur = cur.left;
      } else {
        pred.right = null;  // untread
        visit(cur);
        cur = cur.right;
      }
    }
  }
}