7
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ Only if it is known that the tree is binary. $\endgroup$ Jul 17, 2018 at 9:55

3 Answers 3

12
$\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.)

$\endgroup$
0
-1
$\begingroup$

Yes, another way is to think about the In-order Traversal. You go Left-Root-Right. Well a property of BST is the left node is less than Root and right node is greater than Root. By going in the specified order, you start with the left most sub tree, and work your way over to the right most subtree. This will result in sorted order, else this would be Tree structure, not a Binary Tree Structure.

$\endgroup$
-2
$\begingroup$

It is true only if there are no duplicates.

$\endgroup$
1
  • 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, 2019 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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