While it is true that the inorder traversal of a binary search tree produces a sorted output, is the converse also true, i.e., if the inorder traversal of a binary tree is sorted, then is it necessarily a binary search tree?
While it is true that the inorder traversal of a binary search tree produces a sorted output, is the converse also true, i.e., if the inorder traversal of a binary tree is sorted, then is it necessarily a binary search tree?
if the inorder traversal of a binary tree is sorted, then is it necessarily a binary search tree?
While that exact tree would represent a binary search tree, I'd say that it's not a binary search tree unless the algorithms used to insert and update it maintain that order. Otherwise it's just a binary tree that happened to have a state matching a binary search tree.
@deceptikon
I'm not sure that I got what you meant there.
Let me rephrase my query.
Suppose I have a binary tree T.
I perform inorder traversal on the tree T.
Now, the output I get is sorted, say, 1 2 3 4 5 6 7.
Can I say, the binary tree T that gave this inorder traversal is a binary search tree.
Can I say, the binary tree T that gave this inorder traversal is a binary search tree.
Technically yes, until you make any changes to the tree.