# prove correctness of in-order tree traversal subroutine

I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction.

Claim: For any n-node subtree, the in-order-tree-walk subroutine prints the keys of the subtree rooted at node x in sorted order.

in-order-tree-walk(x)
if(x!=NIL)
in-order-tree-walk(x.left)
print x.key
in-order-tree-walk(x.right)


Above pseudo-code is taken from CLRS, and we're traversing the subtree rooted at node x.

Proof. By ordinary induction. Let our induction hypothesis $$P(n)$$ be the claim itself. We need show $$P(n)$$ holds for all positive integers.

Base case ($$n=1$$): in-order-tree-walk subroutine prints the single node's key and, since the both left and right pointers are NIL, terminates. Trivially, single key is already in sorted order.

Inductive step: Suppose $$P(n)$$ holds for some $$n \geq 1$$. Prove $$P(n+1)$$. Let $$T$$ be subtree consisting of $$n+1$$ nodes. Let $$T'$$ be subtree formed by removing the largest element from $$T$$. $$T'$$ has $$n$$ elements. By induction hypothesis $$P(n)$$, in-order-tree-walk(T') prints keys of subtree rooted at T'.root in sorted order. By binary-search-tree property, largest element in the tree is placed on the rightmost node and it's the last node visited during the in-order-tree traversal. So, that rightmost node's key is printed after the keys of $$T'$$ is printed. Since it's the largest element in $$T$$, and keys of $$T'$$ in printed in sorted order, we can conclude that in-order-tree-walk(T') prints keys of $$T$$ in sorted order.

By induction principle, we can conclude that $$P(n)$$ holds for all positive integers.

Can we show correctness using this induction proof? Is any parts of the proof need to be revised? I appreciate your efforts.

EDIT: trees/subtrees in this post refer to binary search trees. Binary search tree property is preassumed

• You should state clearly in you hypothesis that the tree is a BST. Also, it may be easier to make the induction not on the sizes of the trees, but on the trees themselves. The inductive step would be "Suppose $T = Node(a, k, b)$ a BST where $P(a)$ and $P(b)$ holds, then…" Mar 5 '21 at 10:12

In your proof the largest element of binary search tree $$T$$ can in fact be the root of the tree. I did not check whether you took care of that.
If you want to use induction by a number of elements in the tree, I would advise you to take strong induction, that is the hypothesis assumes the algorithm works for any number less or equal to $$n$$. Then the hypothesis can be applied to both subtrees which must have less elements than the full tree.