5
$\begingroup$

For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Only if it is known that the tree is binary. $\endgroup$ – RemcoGerlich Jul 17 '18 at 9:55
9
$\begingroup$

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.)

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

It is true only if there are no duplicates.

|cite|improve this answer
$\endgroup$
  • 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 at 19:11

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.