BST from two unsorted array

Question

This question was asked in one of the interview : Given two unsorted array, check if it will create the same bst. eg: 2, 1, 4, 0 and 2, 1, 0, 4 will both form same BST.

     2
    / \
   1   4
  /
 0

please suggest some good algo.

Answer 1

• Take the first element - This will be the root (in the above case it is 2)
• All the elements which are lesser than the root element should appear in the same order in both the arrays
  • In the above example, 0 and 1 are the elements lesser than the root elements.
  • In the first array the order is 1, 0
  • Same order is maintained in the second array. So both form the same structure

• All the elements which are greater then the root element should appear in the same order in both the arrays

  • In the above example 4 is the only element greater than 2. It appears in the both the arrays. And hence both the arrays create BST which are structurally the same.

• And of course the very first condition is that both the arrays should contain the same elements but in different order .

Hence this can be solved in linear time.

Pseudocode would be like this:

int GetNextIncresingElement(int[] arr, ref int index, int root)
{
    for(int i = index; i< arr.Length; i++)
    {
        if(arr[i] > root)
        {
            index = i;
            return arr[i];
        }
    }
    return -1;
}

int GetNextDecreasingElement(int[] arr, ref int index, int root)
{
    for(int i = index; i< arr.Length; i++)
    {
        if(arr[i] <= root)
        {
            index = i;
            return arr[i];
        }
    }
    return -1;
}

bool CheckFormsSameBST(int[] arr1, int[] arr2)
{
    int index1 = 1;
    int index2 = 1;
    int num1;
    int num2;

    int root = arr1[0];
    if(root != arr2[0])
        return false;

    while(true)
    {
        num1 = GetNextIncresingElement(arr1, ref index1, root);
        num2 = GetNextIncresingElement(arr2, ref index2, root);     

        if(num1 != num2)
            return false;       
        else
        {
            if(num1 == -1)
                break;
        }   

        index1++;
        index2++;
    }

    index1 = 1;
    index2 = 1;
    while(true)
    {
        num1 = GetNextDecreasingElement(arr1, ref index1, root);
        num2 = GetNextDecreasingElement(arr2, ref index2, root);        

        if(num1 != num2)
            return false;       
        else
        {
            if(num1 == -1)
                break;
        }   

        index1++;
        index2++;
    }

    return true;
}

Answer 2

I agree with the idea Peter and Algorist described. But I believe the sub-trees of each node (represented by the array less than this node and the array larger than it) need to be examined in this fashion as well. For example, 621407 and 621047 yield the same BST but 624017 does not. The function can be written recursively.

sample code added:

bool sameBST(int * t1, int * t2, int startPos, int endPos) {
    int rootPos1, rootPos2;
    if (endPos-startPos<0) return true;
    if (t1[startPos]!=t2[startPos]) return false;
    rootPos1=partition(t1,startPos,endPos,t1[startPos]);
    rootPos2=partition(t2,startPos,endPos,t2[startPos]);
    if (rootPos1!=rootPos2) return false;
    return sameBST(t1,t2,startPos,rootPos1-1) && sameBST(t1,t2,rootPos1+1,endPos);
}

Function partition is the same one you use in quicksort. Apparently, T(n)=2T(n/2)+O(n), which leads to time complexity T(n)=O(nlogn). Because of the recursion, the space complexity is O(logn)