Alg.26 Same BSTs

From algoexpert.io

Write a function to determine whether 2 arrays represent the same BST.



Given 2 arrays, if they are the same, they will satisfy 2 prerequisites:

1. Two arrays have the same length;
2. Two arrays have the same element at their first position.
   Then, we find the elements of the expecting left and right subtrees in the original arrays, recursively check the 2 prerequisites until we get 2 empty arrays. Here is the code implementation:
   

   java

   public static boolean sameBsts(List<Integer> arrayOne, List<Integer> arrayTwo) {
         if (arrayOne.size() != arrayTwo.size()) return false;
         
         if (arrayOne.size() == 0 && arrayTwo.size() == 0) return true;
         
         if (arrayOne.get(0) != arrayTwo.get(0)) return false;
         
         List<Integer> oneLeft = getLeftElements(arrayOne);
         List<Integer> oneRight = getRightElements(arrayOne);
         List<Integer> twoLeft = getLeftElements(arrayTwo);
         List<Integer> twoRight = getRightElements(arrayTwo);
         
     return sameBsts(oneLeft, twoLeft) && sameBsts(oneRight, twoRight);
   }
     
     public static List<Integer> getLeftElements(List<Integer> array) {
         List<Integer> res = new ArrayList<>();
         for (int i = 1; i < array.size(); i++) {
             if (array.get(i) < array.get(0)) {
                 res.add(array.get(i));
             }
         }
         return res;
     }
     
     public static List<Integer> getRightElements(List<Integer> array) {
         List<Integer> res = new ArrayList<>();
         for (int i = 1; i < array.size(); i++) {
             if (array.get(i) >= array.get(0)) {
                 res.add(array.get(i));
             }
         }
         return res;
     }

   Time complexity: O(n^2); Space complexity: O(n^2).

Donate