Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree.

IsSameBST.java

public class IsSameBST {
	public static boolean calculate(int []a, int []b){
		return calculateRecursive(a, b, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	private static boolean calculateRecursive(int []a,int []b, int i_a, int j_b, int min, int max){
		int i;
		int j;
		for(i=i_a;i<a.length;i++)
			if(a[i]>min && a[i]<max) break;
		for(j=j_b;j<b.length;j++)
			if(b[j]>min && b[j]<max) break;
		if(i==a.length && j==b.length) //if does not hit the break then i is now a.length
			return true;
		else if(i==a.length || j==b.length)
			return false;
		else 
			return a[i]==b[j] && calculateRecursive(a,b,i+1,j+1,min,a[i]) && calculateRecursive(a,b,i+1,j+1,a[i],max);
	}
	/**
	 * Inefficient implementation, but easy to understand
	 **/ 
	public static boolean calculateSlow(int []a, int []b){
		if(a.length==0 && b.length==0) return true;
		else if(a.length==0 || b.length==0) return false;
		else return a[0]==b[0]&&calculateSlow(getBiggerElements(a,a[0]),getBiggerElements(b,b[0]))&&calculateSlow(getSmallerElements(a,a[0]),getSmallerElements(b,b[0]));
	}
	private static int[] getBiggerElements(int []a,int n){
		int count=0;
		for(int e:a){
			if(e>n) count++;
		}
		int []ret= new int[count];
		int i=0;
		for(int e:a){
			if(e>n) ret[i++]=e;
		}
		return ret;
	}
	private static int[] getSmallerElements(int []a,int n){
		int count=0;
		for(int e:a){
			if(e<n) count++;
		}
		int []ret= new int[count];
		int i=0;
		for(int e:a){
			if(e<n) ret[i++]=e;
		}
		return ret;
	}
}

IsSameBSTTest.java

public class IsSameBSTTest {
	@Test
	public void testCalculate() {
		assertTrue(IsSameBST.calculate(new int[]{2, 4, 1, 3}, new int[]{2, 4, 3, 1}));
		assertTrue(IsSameBST.calculate(new int[]{8, 3, 6, 1, 4, 7, 10, 14, 13}, new int[]{8, 10, 14, 3, 6, 4, 1, 7, 13}));
		assertFalse(IsSameBST.calculate(new int[]{2, 4, 1, 3}, new int[]{2, 3, 4, 1}));
	}
}