AVL Tree - Print ascending using in-order

Question

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 <= i <= 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.

Answer 1

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.