CareerCup

Assumption: All numbers are distinct (otherwise, you need to tell us about the BST insertion algorithm).

One solution (but essentially same as the tree compare solution in spirit): you can do something like quicksort:

Given Arrays A and B, check if A[0] = B[0] (if not, return false).

Now construct A_more, A_less and B_more, B_less where A_more contains elements of A which are > A[0] (and appear in the same order as they appear in A). This is basically the partition step in quicksort. Note that you need the partition to be stable. It is possible to do that in-place, but is very complex.

Now, recursively compare A_more, B_more and compare A_less and B_less. You can add optimizations to compare lengths of arrays to bail out quicker.

I *think* this should work. When we're inserting any given key, it is always 'perfectly' inserted, that is it is inserted right after the maximum key that is still less than this key.
Given that, we can go through the array and for each value from each array see if we've already inserted it in the other array, and if so if the insertion point is still the same. If not, we know that we would produce two different trees. If so, then we keep looking.

Right now I'm not checking to make sure that both trees contain the same elements, but that should be easy to add.

Also right now the findInsertAfter method does a brute-force search which makes the algorithm n^2, but if you replace that with a sorted data structure and binary search for the optimal element it should be n*log(n).

static boolean willMakeSame(int [] arr1, int [] arr2)
	{
		if(arr1.length != arr2.length || arr1[0] != arr2[0])
			return false;
		
//		int maxSoFar = arr1[0];
//		int minSofar = arr2[0];
//		
		Map <Integer, Integer> insertedAt = new HashMap<>();
		
		for(int at = 0; at < arr1.length; at++)
		{
			if(!insertedAt.containsKey(arr1[at]))
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr1[at]);
				insertedAt.put(arr1[at], insertAfter);
			}
			else
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr1[at]);
				if(insertAfter != insertedAt.get(arr1[at]))
				{
					if(PRINT)
						System.out.println("For arr1 " + at + ", " + arr2[at] + " NOT correctly inserted after " + insertAfter);
					return false;
				}
				else if (PRINT)
					System.out.println("For arr1 " + at + ", " + arr2[at] + " correctly inserted after " + insertAfter);
			}
			if(!insertedAt.containsKey(arr2[at]))
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr2[at]);
				insertedAt.put(arr2[at], insertAfter);
			}
			else
			{
				int insertAfter = findInsertAfter(insertedAt.keySet(), arr2[at]);
				if(insertAfter != insertedAt.get(arr2[at]))
				{
					if(PRINT)
						System.out.println("For arr2 " + at + ", " + arr2[at] + " NOT correctly inserted after " + insertAfter);
					return false;				
				}
				else if(PRINT)
					System.out.println("For arr2 " + at + ", " + arr2[at] + " correctly inserted after " + insertAfter);
			}
		}
		return true;
	}

	private static  int findInsertAfter(Set<Integer> keySet, int i) {
		int maxThatIsSmaller = -1;
		for(int item : keySet)
		{
			if(item > maxThatIsSmaller && item < i)
			{
				maxThatIsSmaller = item;
			}
		}
		return maxThatIsSmaller;
	}

coders-stop.blogspot.in/2012/03/compare-bsts.html

a O(n) time and O(n) space algorithm

typedef std::pair<int, int> PosPair;
typedef std::queue<PosPair> PosPairQueue;

bool check(int a[], int b[], int size) {
  if (size == 0) {
    return true;
  }
  PosPairQueue q;
  q.enqueue(0,0);
  while (!q.empty()) {
    PosPair pp = q.dequeue();
    if ((pp.first == -1 && pp.second != -1) ||
        a[pp.first] != b[pp.second]) {
      return false;
    }

    if (pp.first == -1 && pp.second == -1) {
       continue;
    }
  
    int posGreaterThanA = -1;
    int posLessThanA = -1;
    for (int i = pp.first + 1; 
          i<size && (posGreaterThanA == -1 || posLessThanA == -1); 
          ++i) {
      if (posGreaterThanA == -1 && a[i] > a[pp.first]) {
        posGreaterThanA = i;
      }
      if (posLessThanA == -1 && a[i] < a[pp.first]) {
        posLessThanA = i;
      }
    }

    int posGreaterThanB = -1;
    int posLessThanB = -1;
    for (int i = pp.second + 1; 
          i<size && (posGreaterThanB == -1 || posLessThanB == -1); 
          ++i) {
      if (posGreaterThanB == -1 && a[i] > a[pp.second]) {
        posGreaterThanB = i;
      }
      if (posLessThanB == -1 && a[i] < a[pp.second]) {
        posLessThanB = i;
      }
    }

    q.enqueue({posGreaterThanA, posGreaterThanB});
    q.enqueue({posLessThanA, posLessThanB});
  }
}

What does "making bst from array" mean? More details!

Simple solution (few assumptions made, obviously as question is quite vague):

Input: 2 int arrays
Output: boolean - whether BST constructed from either array will be same

Idea:
- first element has to be equal
- loop till the end of array
- if there is 1 more element left in both arrays, they have to be equal
- advance 1 place
- if there are 2 more elements in the array, they have to be equal when sorted
- if swapped around, each must be on either side of the first element (i.e root of the BST)

public boolean equalBST(int [] A, int [] B) {
    if(A.length != B.length)
        return false;
    if(A[0] != B[0])
        return false;
    
    int root = A[0];
    
    for(int i = 1; i < A.length; i++) {
        if(A[i] == B[i])
            continue;
        else if(i < A.length - 1) {
            if(A[i] == B[i + 1] && A[i + 1] == B[i] && checkSides(A[i], B[i], root)) {
                i++;
                continue;
            }
        }
        return false; 
    }
    return true;
}

private boolean checkSides(int a, int b, int k) {
    if(a < k && b > k)
        return true;
    else if(b < k && a > k)
        return true;
    else
        return false;

}

{#include<stdio.h>
#include<stdlib.h>
#define size 20
int check(int a1[],int a2[],int l,int r)
{
if(r==-1) return 1;
if(a1[l]!=a2[l]) return 0;
if(l==r) return 1;
int b1[r-l+1],b2[r-l+1],b3[r-l+1],b4[r-l+1],k1=-1,k2=-1,k3=-1,k4=-1,i,pivot;
pivot=a1[l];
for(i=l+1;i<=r;i++)
{
if(pivot<a1[i])
b1[++k1]=a1[i];
else
b2[++k2]=a1[i];
if(pivot<a2[i])
b3[++k3]=a2[i];
else
b4[++k4]=a2[i];
}
if(k1==k3 && k2==k4 && check(b1,b3,0,k1) && check(b2,b4,0,k2))
return 1;
else return 0;
}
void main()
{
int a1[]={3,1,0,2,5,4,6};
int a2[]={3,5,6,1,2,4,-1};
int n=sizeof(a1)/sizeof(int);
printf("%d\n",check(a1,a2,0,n-1));
}}
Can we do like this? Here I used extra space. Everytime I am selecting a pivot and putting the elements less than pivot in first array and the elements greater than the pivot in the second array, and recursively checking these arrays.

and for in-place sorting this would work
#include<stdio.h>
void in_place(int a[],int n)
{
int save,i,j,k,pivot;
pivot=a[0];
for(i=1;i<n;i++)
{
if(a[i]<pivot)
{
save=a[i];
for(j=i;a[j]!=pivot;j--);
for(k=i-1;k>=j;k--)
a[k+1]=a[k];
a[j]=save;
}
}
}
void main()
{
int a[]={3,7,8,2,5,4,9,1,6,0};
int n=sizeof(a)/sizeof(int);
in_place(a,n);
int i;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}

Idea is based on qsort-partitioning where order of elements is preserved and done *in place*.
As input function takes 2 arrays, applies partitioning on them and recursively processes each of 2 sub arrays.

public class CompareArraysAsBST {

    public static boolean areBSTEqual(final int[] a, final int[] b) {

        if (a == null || b == null) {
            return false;
        }

        return areBSTEqual(a, 0, a.length - 1, b, 0, b.length - 1);
    }

    /**
     * Returns true if 2 arrays are BST equal from index start to index end inclusive.
     */
    private static boolean areBSTEqual(final int[] firstArr, final int firstStart, final int firstEnd,
            final int[] secondArr, final int secondStart, final int secondEnd) {

        // indexes have to be always the same for both arrays
        if (firstStart != secondStart || firstEnd != secondEnd) {
            return false;
        }

        // if we are outside of the array then ok
        if (firstStart >= firstArr.length && secondStart >= secondArr.length) {
            return true;
        }

//if first indexes are bigger than end ones return true
         if (firstStart > firstEnd || secondStart > secondEnd) {
            return true;
        }


        // if first elements of the array are not the same then arrays are not BST same
        if (firstArr[firstStart] != secondArr[secondStart]) {
            return false;
        }

        int firstBorder = partition(firstArr, firstStart, firstEnd);
        int secondBorder = partition(secondArr, secondStart, secondEnd);

        // recursive invocation on 2 pieces of an array exclusive the first one (we checked it already)
        boolean areEqualLeft = areBSTEqual(firstArr, firstStart + 1, firstBorder - 1, secondArr, secondStart + 1,
                secondBorder - 1);
        boolean areEqualRight = areBSTEqual(firstArr, firstBorder, firstEnd, secondArr, secondBorder, secondEnd);

        return areEqualLeft && areEqualRight;
    }

    /**
     * Sorts an array in qsort way but elements' order is presumed.
     * Returns an index of the first element that is *bigger* than a[begin]
     */
    private static int partition(final int[] a, final int start, final int end) {

        // loop invariant: res is always pointing to the first element *bigger* than a[begin]
        int res = start + 1;
        for (int i = start + 1; i <= end; i++) {

            // if found an element that is less than a[begin] then circularly shift the sub array of elements
            // example: 4 1 3 5 8 2 7, res = 3 (a[res] = 5), i = 5 (a[i] = 2) -> shift the sub array {5 8 2} -> {2 5 8}
            // so that array becomes 4 1 3 2 5 8 7 and res = 6 (a[res] = 5)
            if (a[i] <= a[start]) {
                swapWithShift(a, res, i);
                ++res;
            }
        }

        return res;
    }

    private static void swapWithShift(final int[] a, final int start, final int end) {
        int tmp = a[end];
        for (int i = start; i <= end; i++) {
            int tmp2 = a[i];
            a[i] = tmp;
            tmp = tmp2;
        }
    }

    public static void main(final String[] args) {
        assertThat("", areBSTEqual(new int[] {2, 1, 3}, new int[] {2, 3, 1}), is(true));
        assertThat("", areBSTEqual(new int[] {5, 1, 3, 4, 8, 7, 6}, new int[] {5, 8, 1, 3, 7, 6, 4}), is(true));
        assertThat("", areBSTEqual(new int[] {3, 2, 3}, new int[] {2, 3, 1}), is(false));
        assertThat("", areBSTEqual(new int[] {2, 1, 3, 5}, new int[] {2, 3, 1}), is(false));
        assertThat("", areBSTEqual(new int[] {4, 2, 3, 1, 7}, new int[] {4, 2, 1, 3, 7}), is(true));
        assertThat("", areBSTEqual(new int[] {}, new int[] {}), is(true));
        assertThat("", areBSTEqual(null, null), is(false));
    }
}

the algo i thought...i will call a fn with 2 arrays A and B with same length n say with min=INT_MIN and max=INT_MAX,index1=0,index2=0
1. now starting from index1 in A and index2 in B,find 1st element in both arrays greater than min and less than max.If no such element in both the arrays,return true...If such element is only in 1 array return false.let index of such element in array A is i1 and array B is i2. If both elements are not same return false
2. call the same fn twice
return
isSameBST(A,B,A[i1],max,i1+1,i2+1) &&
isSameBST(A,B,min,A[i1],i1+1,i2+1).

My solutions in C++:

#include <iostream>
#include <vector>

using namespace std;

/* Recursive version */
int sameBST(vector<int> A, vector<int> B) {
    if (A.size() != B.size())
        return 0;
    if (A.size() == 0)
        return 1;
    if (A[0] != B[0])
        return 0;
    vector<int> Ainf, Asup, Binf, Bsup;
    for (int i = 1; i < A.size(); ++i) {
        if (A[i] <= A[0])
            Ainf.push_back(A[i]);
        else
            Asup.push_back(A[i]);
        if (B[i] <= A[0])
            Binf.push_back(B[i]);
        else
            Bsup.push_back(B[i]);
    }
    return sameBST(Ainf, Binf) && sameBST(Asup, Bsup);
}

void swap(vector<int>& L, int i, int j) {
    int tmp = L[i];
    L[i] = L[j];
    L[j] = tmp;
}

/* Partitioning version */
int sameBST(vector<int>& A, vector<int>& B, int Astart = 0, int Bstart = 0, int Aend = -1, int Bend = -1) {
    if (Aend == -1)
        Aend = A.size() - 1;
    if (Bend == -1)
        Bend = B.size() - 1;
    if (Bend - Bstart != Aend - Astart)
        return 0;
    int length = Aend - Astart + 1;
    if (length == 0)
        return 1;
    if (A[Astart] != B[Bstart])
        return 0;
    int cntAinf = 0, cntBinf = 0;
    for (int i = 1; i < length; ++i) {
        if (A[Astart + i] <= A[Astart]) {
            swap(A, Astart + i, Astart + cntAinf + 1);
            ++cntAinf;
        }
        if (B[Bstart + i] <= A[Astart]) {
            swap(B, Bstart + i, Bstart + cntBinf + 1);
            ++cntBinf;
        }
    }
    return sameBST(A, B, Astart + 1, Bstart + 1,
                   Astart + cntAinf, Bstart + cntBinf)
            &&
           sameBST(A, B, Astart + cntAinf + 1, Bstart + cntBinf + 1,
                   Aend, Bend);
}

"A1[]={2,1,3}
2
1 3

A2[]={2,3,1}
2
1 3"

How are these really the same? Depending on the rules, the second number could always be the left parent and the third number could be the right parent. According to my rules, it would be

2
1 3

2
3 1

Totally different.

public boolean isIdenticalBST(int[] A, int[]B) {
	    return checkIdenticalBST(A, 0, B, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	// helper function to check if elements of array A from aPos index and elements of array B from bPos index 
	// which are in the range between min and max can create identical BST 
	private boolean checkIdenticalBST(int[] A, int aPos, int[] B, int bPos, int min, int max) {
		if (aPos == -1 && bPos == -1) {
			return true;
		}
		if (aPos == -1 || bPos == -1) {
			return false;
		}
		// check value of the first element
		if (A[aPos] != B[bPos]) {
	        return false;
	    }
		// then check the subset of smaller elements then greater elements
		return checkIdenticalBST(A, findFirstInRange(A, aPos + 1, min, A[aPos]), 
							   B, findFirstInRange(B, bPos + 1, min, A[aPos]), 
							   min, A[aPos]) 
			   && 
			   checkIdenticalBST(A, findFirstInRange(A, aPos + 1, A[aPos], max), 
							   B, findFirstInRange(B, bPos + 1, A[aPos], max), 
							   A[aPos], max);
	}

	// find first index of element that between min and max, if not found return -1
	private int findFirstInRange(int[] arr, int pos, int min, int max) {
		while (pos < arr.length) {
			if (arr[pos] > min && arr[pos] < max) {
				return pos;
			}
			pos++;
		}
		return -1;	
	}

Please share feedback on this approach
1. Check length of both the arrays.
1. if both are of equal length, sort them (we can do it in lg n) and then compare each element. If we find a mismatch, then both BSTs are not identical.

Please share feedback on this approach
1. Check length of both the arrays.
1. if both are of equal length, sort them (we can do it in lg n) and then compare each element. If we find a mismatch, then both BSTs are not identical.

This doesn't use any additional data structure and uses recursion.

public class EqualBST {

	/**
	 * @param args
	 */
	static int[] a={7,9,10,5,2,7};
	static int[] b={7,5,9,10,7,2};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		boolean isBST=compareBST(0,0);
		if (isBST)
			System.out.println("It is a BST");
		else
			System.out.println("Not a BST");
	}
	public static boolean compareBST(int i, int j){
		if(i >= a.length && j>=b.length){
			return true;
		}
		int k,l,left1 = 0,left2=0,right1=0,right2=0;
		for(k =i+1;k<a.length;k++){
			if(a[k]<a[i])
				left1=a[k];
		}
		for(l=j+1;l<b.length;l++){
			if(b[l]<b[j])
				left2=b[l];
		}
		if(left1 != left2) return false;
		if(compareBST(k,l)){
			for(k =i+1;k<a.length;k++){
				if(a[k]>a[i])
					right1=a[k];
			}
			for(l=j+1;l<b.length;l++){
				if(b[l]>b[j])
					right2=b[l];
			}
		}
		if(right1 != right2) return false;
		return(compareBST(k,l));
	}
}

You could visualize subarrays of each array as a level in the tree. subarray[0] will be root. subarray[1, 2] will be first level subarray[3, 4, 5, 6] will be second level etc.

All you need to verify is that for a given subarray of the first array the corresponding subarray of the second is a valid rotation. Below is a python code.

def form_same_bst(arr1, arr2):
    if len(arr1) != len(arr2):
        return False
    n = len(arr1)
    i = 1
    while i < n:
        start = i-1
        end = 2*i - 1
        if not are_rotations(arr1[start:end], arr2[start:end]):
            return False
        i *= 2
    return True


def are_rotations(arr1, arr2):
    arr = arr1 * 2
    n = len(arr1)
    i = 0
    result = False
    while i < n and not result:
        result = True
        for j in range(n):
            if arr[i + j] != arr2[j]:
                result = False
                break
        i += 1
    return result

print(form_same_bst([2, 4, 3, 1, 5, 6, 7], [2, 3, 4, 5, 6, 7, 1]))

This question can not be answered without knowledge of the BST construction algorithm. Since none is given I would devise my own: Sort the array, then construct the BST.
In that case, the problem is trivial. Two arrays have the same BST if they contain the same elements. This can be answered in O(n) time by using two hashmaps and intersecting them.

2 bsts would not be identical

2 bsts would not be identical

First Element and size of both array should be same.
All the element smaller than first element should be in same Order in both array.
Slly: all the element greater than first element should be in same Order in both array.

(Assuming : all different element in array
n1:- size of A1
n2:- size of A2
)

Boolean function(){
if((n1 != n2) && (A1[0] != A2[0]))
  return false;
int i=0,j=0;

while(i<n1 || j<n1){
  while(i<n1){
     if(A1[i]>A1[0])
        i++;
  }
  while(j<n1){
     if(A2[j]>A2[0])
        j++;
  }
  if(A1[i++] != A2[j++])
      return false;
}// end of while


i=0;j=0;

while(i<n1 || j<n1){
  while(i<n1){
     if(A1[i]<A1[0])
        i++;
  }
  while(j>n1){
     if(A2[j]>A2[0])
        j++;
  }
  if(A1[i++] != A2[j++])
      return false;
}// end of while

return true;
}// end of function

1) check whether the size of both the arrays are equal.
2)if equal, then simply sort both arrays.
3)compare both the element in linear order.see a flag to track all the elements are equal are not.

If BST trees are equal, it means that the inorder of the both trees should be equal. Inorder means sorting. So sort the both arrays , and compare.