Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If the height is $0$ it is true.
Assume that all binary trees for which inorder is sorted and height smaller than $h$ are BST.
Consider a tree with root $x$, height $h$ and its inorder is sorted. In particular its left and right subtrees' inorder are sorted and have height smaller than $h$. Then, by the assumption, they are BST. Now, in the inorder of the given tree, the node $x$ is listed after all nodes of its left subtree. Since its inorder is sorted, then $x$ is not smaller than any node of its left subtree. Likewise, $x$ is not larger than any node of its right subtree. Therefore, the tree is a BST.
Hence, by induction on the height of the binary tree, all binary trees for which inorder is sorted are BST.
