AVL Tree - Print ascending using in-order Trying to understand how to write proof of correctness.
Searched over the internet on how to write proof of correctness but can't find a good solution for it.

The following sorting algorithm is proposed using the AVL tree: AVL input of all elements, and printing them in order.

Algorithm  - Sort AVL (A[1..n])

T -> Empty AVL Tree.


for each 1 &lt;= i &lt;= n

insert A[i] to T.

print T elements by using in-order fashion.


Prove the correctness of the algorithm by showing the in-order scan of binary tree is always in ascending order.
AVL trees, like all other binary search trees, have the following guarantee:


  Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.


Using this, you can easily prove by induction that the inorder traversal of a binary search three produces a list of keys in nondecreasing order.