recategorized by
663 views
1 votes
1 votes
a:) If given Tree is BST => Inorder of keys is sorted

b:) Inorder of keys is sorted => Tree is BST(converse of above)

I know first one holds.Is second one also true?If not can someone give counter example?
recategorized by

1 Answer

1 votes
1 votes

Suppose we have a tree with n keys with values 1 to n.

The inorder of this tree is 1, 2, 3,...,n and we are not sure if this is a BST or not.

We can have a total of n! different pre-order traversals for this tree and if we can prove that for all such preorder traversals, the tree produced is BST then we can effectively claim that if the inorder traversal is sorted, the tree must be BST.

Now for each pre-order traversal, the first element in the traversal will be the root of the tree and in the left sub tree of the root, all the nodes less than root will be present and n the right sub tree, all the nodes greater than root will be present.

For ex - 1,2,3,4,5,6 be the nodes then if 4 is the root then 1,2,3 must be present in left sub tree and 5,6 must be present in right sub tree.

Again, continuing in a generic way, suppose we had chosen k as the root in the first step, then we will have 1 to k-1 elements for the LST and k+1 to n for the RST. Now, the LST has reduced to a smaller problem where the inorder is 1 to k-1 and (k-1)! preorder traversals are possible and similarly, RST has reduced to a problem where inorder is k+1 to n and (n - k)! preorder traversals are possible. Whatever maybe the left child and right child of the root based on above argument, left child<root<right child. We can recursively then show that each node of this tree will follow the same property, i.e. left-child of the node<node<right child of the node because for every node, the inorder traversal is sorted and it will be a smaller subproblem of the initial problem and thus will maintain the binary search property all the way down.

So, it can be said that if the inorder traversal is sorted, the given tree is definitely a BST.

Related questions

0 votes
0 votes
1 answer
1
once_2019 asked Jun 24, 2018
609 views
Is the root node an internal node?
0 votes
0 votes
0 answers
2
vijju532 asked Jun 13, 2018
188 views
how does linux kernel uses the red black tree property ???elabourate
–4 votes
–4 votes
2 answers
3
Souvik33 asked Oct 27, 2022
602 views
*MSQ*The following figure depicts a a. A tree and only treeb. A tree with 3 nodesc. A graph (Since every tree is a graph)d. A graph and only graph
0 votes
0 votes
3 answers
4
smartmeet asked Feb 8, 2017
6,895 views
If a node in a BST has two children, then its in-order predecessor hasa) No left childb) No right childc) 2 childrend) no child