For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?
$\begingroup$
$\endgroup$
-
2$\begingroup$ Only if it is known that the tree is binary. $\endgroup$ – RemcoGerlich Jul 17 '18 at 9:55
$\begingroup$
$\endgroup$
Yes.
The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.
Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.
But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.
Thus, there's a contradiction, and such a tree cannot exist.
(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)
$\begingroup$
$\endgroup$
It is true only if there are no duplicates.
-
3$\begingroup$ This limitation of no duplicates is not in the other answer. Could you edit your answer to explain how this can fail when there are duplicates, with e.g. a counterexample? $\endgroup$ – Discrete lizard♦ Apr 11 '19 at 19:11
