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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.