# If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

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

• Only if it is known that the tree is binary. – RemcoGerlich Jul 17 '18 at 9:55

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

It is true only if there are no duplicates.

• 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? – Discrete lizard Apr 11 '19 at 19:11