I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown [here][1], 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][2], and we're traversing the subtree rooted at node x.<br>

> Proof. By ordinary induction. Let our induction hypothesis $P(n)$ be the claim itself. We need show $P(n)$ holds for all positive integers.<br><br>
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.<br><br>
 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.<br><br>
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.


  [1]: https://cs.stackexchange.com/questions/12610/question-about-the-formal-proof-of-the-inorder-traversing
  [2]: https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844