Repeated right rotations expose the next inorder entry without a recursion stack:A right rotation replaces a local shape with inorder order by another shape with exactly that same order. The inner loop therefore preserves the inorder sequence of the remaining tree while moving its next output closer to the root. When the left child is null, the root is exactly the first remaining inorder entry. Printing it and advancing to its right child removes that entry from the remaining traversal.
def printDestructively(input: Tree): Unit = {
var root = input
while (root != null) {
while (root.left != null) {
val child = root.left
root.left = child.right
child.right = root
root = child
}
println(root.datum)
root = root.right
}
}The outer-loop invariant is that the output already produced, followed by the inorder sequence of the current root, equals the original inorder sequence. Consequently the procedure prints every original entry once in order. It stores only a constant number of node references and uses auxiliary space. It changes the original links, as permitted; clients must not rely on the input tree retaining its earlier shape.
Articles by others on the same topic
There are currently no matching articles.