0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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…" $\endgroup$ – Nathaniel Mar 5 at 10:12
0
$\begingroup$

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.

Finaly you could use structural induction, that is induction using the inductive definition of the structures you consider. Here that is the notion of a binary tree: which is either empty, or a root and two subtrees. In practise this gives the same proof as strong induction, but you did not need to quantify the number of nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.