Check identical Binary Search Tree (BST)

By | February 16, 2016

Check identical Binary Search Tree (BST) without building a tree

Problem statement to check identical Binary Search Tree (BSTs) without building a tree.

We are given two arrays of integers from each of which we have to make a binary search tree(BST). We need to determine whether these binary search trees (BSTs) will be identical or not without actually constructing the tree.

Example for testing if 2 Binary Search Trees (BSTs) built from different arrays are identical:

Input: Array 1 {7, 5, 10, 3, 6, 8, 12, 4, 11}
       Array 2 {7, 10, 8, 12, 5, 11, 6, 3, 4}

Output: Same BST
                7
             /     \
            5        10
          /   \     /   \
         3     6   8     12
          \              /
            4           11

Solution to check identical Binary Search Tree (BST):

According to binary search tree (BST) property, elements of left subtree must be smaller than the root and elements of right subtree must be greater than the root.
Two arrays are identical binary search trees if for every element x, the elements in left and right subtrees of x appear after it in both arrays. And same is true for roots of left and right subtrees.
Here we use Divide and Conquer method.We check if next smaller and greater elements are same in both arrays. Same properties are recursively checked for left and right subtrees.

Algorithm to check binary search tree built from the array are same:

  1. Start checking at the first element of both the arrays.
  2. The elements should also lie in the range of maximum and minimum values.
  3. The elements of both the arrays may
    1. Be the last elements (having no children ) of their respective arrays. In such a case, return true.
    2. Have different children or only one array might have child elements.In this case, return false.
  4. Make the curent element parent and check the array for left subtree and the right subtree recursively.

Check identical Binary Search Tree (BST) without building a tree code in c++

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

/*Function to check if the arrays are identical*/
bool CheckIfIdentical(int a[], int b[], int n, int counter1, 
int counter2, int min, int max)
{
   int i,j;

   /*Check if value lies in range of max and min.*/
   for (i=counter1; i<n; i++)
       if (a[i]>min && a[i]<max)
           break;
   for (j=counter2; j<n; j++)
       if (b[j]>min && b[j]<max)
           break;
 
   /* If the parent element is last in both arrays 
      i.e. it has no children elements */
   if (i==n && j==n)
       return true;
 
   /* Return false if any of the following is true
      a) If the parent element has children in one 
      array, but not in the other.
      b) If the child elements are not same. */
  
   /* ^ depicts XOR function which returns
      0 if both elements are similar */  
   if (((i==n)^(j==n)) || a[i]!=b[j])         													
       return false;
 
   /* Make the current child as parent and recursively
      check for left and right subtrees of it. Note that 
      we can also pass a[j] in place of a[i] as they are 
      both are same */
       
    /* Right Subtree*/
   return CheckIfIdentical(a, b, n, i+1, j+1, a[i], max) && 
    /* Left Subtree*/
          CheckIfIdentical(a, b, n, i+1, j+1, min, a[i]);   
}

/*Driver Function to test above program*/
int main() {
   int a[] = {7, 5, 10, 3, 6, 8, 12, 4, 11};
   int b[] = {7, 10, 8, 12, 5, 11, 6, 3, 4};
   int n = sizeof(a)/sizeof(a[0]);
 	
   if (CheckIfIdentical(a,b,n,0,0,INT_MIN,INT_MAX))
      cout<<"The given arrays are Identical";
   else
      cout<<"The given arrays are Not Identical";
   return 0;
}

OUTPUT:

The given arrays are Identical

 Time Complexity:

Average Case: O(nlogn)
WorstCase     : O(n2)