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 BST as shown below

binary-search-tree
 


 
 
C++ implementation –
 

Download   Run Code

Output:

Given keys represent same BSTs

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

 
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

Notify of
avatar
wpDiscuz