1
$\begingroup$

An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the tree was a BST? (Is it a necessary and sufficient condition?)

I was looking for an algorithm to check if a given binary tree is a BST or not with the best time complexity. One of the solutions here suggested to do an in-order traversal and verify if the sequence is sorted. But I don't understand why this is a necessary and sufficient condition. I need a clear and rigorous proof.

I appreciate any help!

$\endgroup$

1 Answer 1

2
$\begingroup$

Indeed. A binary tree is a BST iff its inorder traversal is sorted.

First: when is a binary tree a binary search-tree (BST)? I for any node of the tree all nodes in its left subtree are less than the root, while all nodes in the right subtree are larger than the root.

The inorder traversal of a binary tree is recusively defined as LNR: visit left subtree, visit node, visit right subtree. Thus for any node, the inorder traversal visits all nodes in its left subtree before that node, followed by the right subtree. This holds for all nodes in the tree, even though in the final list we cannot recognize the subtrees anymore.

Hence, if the inorder traversal is sorted it implies that all nodes in a left subtree are smaller than the root of the tree, because all left nodes were listed before the root of that subtree. Symmetrically for the right subtree.

Rigorous enough for me, I hope it is clear for you.

$\endgroup$

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.