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?
Trees/subtrees in the above refer to binary search trees. Binary search tree property is assumed.
