Use the empty reference as the base case:Induction on the tree proves the order: the first recursive call prints exactly the left subtree, then the procedure prints the root, then the final call prints exactly the right subtree. A finite acyclic tree supplies decreasing proper subtrees, so the recursion terminates. The traversal is valid for arbitrary integer labels; sorted output would additionally require a binary search tree invariant.
def printInorder(root: Tree): Unit = {
if (root != null) {
printInorder(root.left)
println(root.datum)
printInorder(root.right)
}
}Split the index range at its middle:For , the child sizes are and , differing by at most one. Induction gives the same property at every descendant, so the result is nearly balanced. Its inorder traversal is the initial subrange, then , then the final subrange, reproducing exactly with every occurrence retained.
def MakeTree(u: Array[Int], a: Int, b: Int): Tree = {
require(0 <= a && a <= b && b <= u.length)
if (a == b) null
else {
val middle = a + (b - a) / 2
new Tree(u(middle),
MakeTree(u, a, middle),
MakeTree(u, middle + 1, b))
}
}There is one nonempty recursive call per constructed node and one constant-time base call per empty child position. Therefore construction takes time for , or including the empty case, and allocates exactly nodes. The balanced recursion has logarithmic stack depth. The input array need not be sorted: the required property concerns subtree sizes and inorder order, not a search-tree ordering.
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.
For a remaining tree , define the potentialThis counts the nodes not on the right spine, so . Consider a right rotation with old root , left child , and three untouched subtrees . Before the rotation the potential isAfter the rotation it is , so each rotation decreases by exactly one while preserving the number of remaining nodes. This supplies a nonnegative decreasing bound for the inner loop.
When the root has no left child, printing it and advancing to its right child leaves unchanged and decreases the remaining node count by one. Thus decreases on every rotation and every removal, proving termination of the whole procedure. Over the entire execution there are exactly printed nodes and exactly rotations, since the final potential is zero. Both quantities are at most , so the running time is for a nonempty tree, with constant auxiliary space. The nested syntax does not imply quadratic time: it is the total potential decrease across all iterations that bounds the inner work. The potential is a proof device and is not computed by the running program.
Articles by others on the same topic
There are currently no matching articles.