Thursday, March 22, 2012

[Amazon Interview] Compare the BSTs


Given two unsorted integer arrays, your task is to compare the BST formed by both the arrays.

e.g [3 2 1 4 5] & [3 4 2 5 1]
when the BST is formed by taking the elements from the left, both BST turn out to be same.

         3
        /  \
      2     4
     /         \
    1           5

Expected time complexity O(n).