Inorder traversal

An inorder traversal of a binary tree uses recursion to visit the left subtree, output the current vertex, and visit the right subtree; an empty subtree outputs nothing. This is a depth-first traversal of a tree with output between the two recursive calls. It produces sorted keys for a binary search tree, but arbitrary labels in a binary tree need not appear in total order.

// Target: computer-science.bigb

While the remaining root has a left child, apply a right tree rotation there. Once the left child is null, output the root and advance to its right child. The output already produced followed by the remaining inorder sequence is invariant. There are exactly $N$ output removals and $L(T_0)\le N$ rotations, because rotations decrease the left-size potential and removals preserve it. The algorithm therefore takes linear time and constant auxiliary pointer space, at the cost of changing the input links.