Check if given keys represents same BSTs or not without building the BST

Given two arrays which represents set of BST keys, check if they represents same BSTs or not. We are not allowed to build the tree.

 

For example, consider below arrays


X[] = { 15, 25, 20, 22, 30, 18, 10, 8, 9, 12, 6 }
Y[] = { 15, 10, 12, 8, 25, 30, 6, 20, 18, 9, 22 }

Both arrays represents same BSTs as shown below –

binary-search-tree
 

 
C/Java Implementation –

C

Download   Run Code

Output:

Given keys represent same BSTs

Java

Download   Run Code

Output:

Given keys represent same BSTs

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).
 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek Sharma
Guest

Line nos 37 and 38:
37: leftY[] will contain all elements less than Y[0]
38: if(Y[i] < X[0])

Abhsihyam
Guest

I can solve the same problem by using map also right??

anuj
Guest

What would be the time complexity if given bsts are skewed tress?

tju
Guest

Intuitively I feel that the set of keys X equals set of keys Y iif they have the same BST. So just checking that the 2 arrays have the same key should determine if they yield the same BST.

What’s wrong with that approach?

vinith
Guest

you should declare all four arrays leftx,lefty,rightx,righty after all the base conditions because when n==0 left[n-1] which will be left[0-1] i.e,left[-1] will produce runtime error