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?

2
Contributors
3
Replies
4
Views
6 Years
Discussion Span
Last Post by deceptikon

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.