patternModerate
If inorder traversal of a tree is in ascending order will the tree definitely be a BST?
Viewed 0 times
orderthebstinorderwilldefinitelytreeascendingtraversal
Problem
For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?
Solution
Yes.
The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.
Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.
But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.
Thus, there's a contradiction, and such a tree cannot exist.
(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)
The proof is straightforward. Assume you have a tree with a sorted in-order traversal, and assume the tree is not a BST. This means there must exist at least one node which breaks the BST assumption; let's call this node $v$.
Now, there are two ways $v$ could break the BST assumption. One way is if there's a node in $v$'s left subtree with label greater than $v$. The other way is if there's a node in $v$'s right subtree with label less than $v$.
But everything in $v$'s left subtree must come before it in the in-order traversal, and everything in its right subtree must come after it. And we assumed that the in-order traversal is sorted.
Thus, there's a contradiction, and such a tree cannot exist.
(EDIT: As RemcoGerlich points out, this is only true if your tree is known to be binary. But if it's not binary, an in-order traversal isn't defined, afaik.)
Context
StackExchange Computer Science Q#95329, answer score: 12
Revisions (0)
No revisions yet.