= Solution
Use <destructive inorder traversal by right rotations>. A <right tree rotation> preserves <inorder traversal> but moves the first unvisited node closer to the root:
``
PROCEDURE InorderDestructive(t: Tree; p: Visit);
VAR q: Tree;
BEGIN
WHILE t # NIL DO
WHILE t.left # NIL DO
q := t.left;
t.left := q.right;
q.right := t;
t := q
END;
p(t.label);
t := t.right
END
END InorderDestructive;
``
The outer <loop invariant> states that the labels already passed to `p`, followed by the <inorder traversal> of `t`, equal the original <inorder traversal>. The remaining nodes form a <binary tree> disjoint from the nodes already visited. The inner <loop invariant> preserves the remaining <inorder traversal>: if the old root is $y$, its left child is $x$, and the three unchanged <subtrees> are $A,B,C$, then both shapes have order $A,x,B,y,C$.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-resit-2015-inorder-rotation.png]
{title=A <right tree rotation> preserves <inorder traversal> and exposes the next node}
At inner-loop exit, `t.left = NIL`, so the root is the first remaining node. Visiting it and replacing `t` by `t.right` preserves the outer <loop invariant>. The procedure changes child <pointers> and makes the old root reference unusable as the original <binary tree>. Assume `p` neither changes the <binary tree> nor depends on its old shape.
$$
\boxed{\text{Every label is visited in inorder using }O(1)\text{ auxiliary space}.}
$$
Back to article page
