Check for Identical BSTs without building the trees

Problem Statement

“Check for identical BSTs without building the trees” problem states that you are given two arrays that represent some nodes. So we create BSTs from both of the arrays now we need to tell if the BSTs created from these arrays will be identical or not? The catch here is we cannot create the trees (i.e. we cannot construct the trees and then compare them). We need to somehow check if they are the same or not without constructing a tree.

Example

Arr1[] = {2, 1, 4, 3, 5}

Arr2[] = {2, 4, 5, 3, 1}

Yes

Explanation: On constructing the trees both of them look the same and thus they are said to be identical.

Approach for Check for Identical BSTs without building the trees

We will use recursion to solve this problem. Here we will use some basic properties of binary search trees which are that all elements in the left subtree are smaller than root. While all elements on the right of the root are larger than it. So, we will check if the root of both the trees is the same, and the children of the root come after it in the array sequence. So root is present before its children in both the arrays. This condition should be satisfied for the left and right subtree as well.

This can be done recursively. So we write a function that will call itself to check if the left subtrees are identical and the same goes for the right subtree. When all of these conditions pass, we say that the binary search trees represented by both the arrays are identical.

Code

C++ code for Check for Identical BSTs without building the trees

#include <bits/stdc++.h>
using namespace std;

// this function checks if the BSTs are identical or not
// Here the i1 & i2 represent the indices in the arrays arr1 and arr2
// The minimum & maximum are used for defining the bounds of left and right subtree
bool areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum)
{
    // find the first element in a which lies between minimum and maximum value
    // here we find the node which becomes the root of either the left or right subtree
    // depending upon the value of minimum and maximum
  int j, k;
  for (j = i1; j < n; j++)
  if (arr1[j] > minimum && arr1[j] < maximum)
    break;
  for (k = i2; k < n; k++)
    if (arr2[k] > minimum && arr2[k] < maximum)
      break;


    // base case
    // current node is a leaf in both the trees
    if (j==n && k==n)
        return true;

    bool oneLeafOtherNonLeaf = ((j==n)^(k==n));
    // current node is leaf in one of the trees but not in other.
    // the first number which satisfy the given constraint must be same in both the arrays
    // because they serve as root of the subtrees
    if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
        return false;

    // recursively solve for left and right subtree
    return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
}

int main()
{
    int arr1[] = {2, 1, 4, 3, 5};
    int arr2[] = {2, 4, 5, 3, 1};
  int n=sizeof(arr1)/sizeof(arr1[0]);
  bool answer = areBSTsIdentical(arr1, arr2, n, 0, 0, INT_MIN, INT_MAX);
  cout<<(answer ? "YES" : "NO");
  return 0;
}

YES

Java code for Check for Identical BSTs without building the trees

class Main
{ 

  // this function checks if the BSTs are identical or not
  // Here the i1 & i2 represent the indices in the arrays arr1 and arr2
  // The minimum & maximum are used for defining the bounds of left and right subtree
  static boolean areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum) 
  { 
    // find the first element in a which lies between minimum and maximum value
      // here we find the node which becomes the root of either the left or right subtree
      // depending upon the value of minimum and maximum
    int j, k;
    for (j = i1; j < n; j++)
    if (arr1[j] > minimum && arr1[j] < maximum)
      break;
    for (k = i2; k < n; k++)
      if (arr2[k] > minimum && arr2[k] < maximum)
        break;
  
  
      // base case
      // current node is a leaf in both the trees
      if (j==n && k==n)
          return true;
  
      boolean oneLeafOtherNonLeaf = ((j==n)^(k==n));
      // current node is leaf in one of the trees but not in other.
      // the first number which satisfy the given constraint must be same in both the arrays
      // because they serve as root of the subtrees
      if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
          return false;
  
      // recursively solve for left and right subtree
      return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
  } 
  
  public static void main(String[] args) 
  {
    int arr1[] = {2, 1, 4, 3, 5};
    	        int arr2[] = {2, 4, 5, 3, 1};
    int n=arr1.length; 
    boolean answer = areBSTsIdentical(arr1, arr2, n, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.print(answer ? "YES" : "NO");
  } 
}

YES

Complexity Analysis

Time Complexity

O(N) because we just traversed both the arrays, even though we called recursion. But then too we ran the recursion over the array with one state as index, which ensured linear time complexity.

Space Complexity

O(N) because we used an array to store the input. Other than that we have used just some constant number of variables. So the algorithm itself uses only O(1) extra space but the program as a whole has linear space complexity.