CareerCup

construction of BST would take nLogn time, given that both has same no of elements

so On is difficult to achieve, though there are certain checks that we can impose to quit early

[1] if the length of the two arrays are different then they can not be identical
[2] Construction of BST mostly depends on the order of the elements they come (unsorted)
keep track of the height of each tree (since we are not building height balanced tree) if the height of tree with same no of elements inserted then its unlikely that they will be same later

by the way did you happen to aswer it in On time? or the interviewer was emphasizing to be in On

What do you mean by comparing two BSTs ????

In what manner are these trees constructed from the arrays?

In this case, we do not need to construct the BST.
1. If both arrays' values and their ordering patterns with in each array is same, both arrays would construct similar BST. O(n).
2. If values are not identical but both arrays follows similar ordering pattern , structure will be same but not the values. ex: A1: 1,2,3 n A2: 4,5,6 or A1: 9,5,11 or A2: 3,1,4 ...structures of two BSTs in each example would be same but not the values.

I think question comes down to ensuring same size, similar values , and similar ordering pattern among values of each array.

hey...tell me whether dis algo is working or not....take one count variable for each array and traverse array...if in array succedng value is less than cur value do -1 if grtr do +1 aftr trvrsng both array chck deir count value if they r same dey form same bst...dis algo is to be applied when both arrays has similar values and same length

hey..tell me whether dis algo will work or not...take one count variable for both arrays...now start trvrsng first array if next elemnt is less than current do count=count-1 else add 1...do same for second array...if both count value r same dey form same bst....dis one has to be done aftr chckng same value in both arrays,equal length and first elmnt is also equal....

//Convert array to BST and Compare

SortArray(int array[],int start , int end)
{
if(start >end)
return NULL;
mid = (start + end)/2;

BinaryTree *node = new BinaryTree(a[mid]);
node -> left = SortArray(a,start,mid-1);
node -> right = SortArray(a, mid+1, end);

return node;
}

isSame( BinaryTree *t1, Binary *t2)
{

if(t1 == NULL && t2 == NULL)
return TRUE;

else if(t1 != NULL && t2 != NULL)
{
return ( (t1->data == t2->data) && (isSame(t1->left,t2->left)) && (isSame(t1->right , t2->right)));
}
else

retrurn false;
}



int main()
{
BinaryTree *t1 = SortArray( a1,0,n-1);
BinaryTree *t2 = SortArray( a2,0,n-1);

result = isSame(t1,t2);
}

print inorder traversal of both BST formed from the 2 unsorted arrays. comapare the 2 inorder traversal. In this case though 2 arrays structure are need not to be same . But then BST will be same . so BST will give the same inorder traversal .

Note :I am just sharing my ideas. I m not sure of this

Use Dis Algo to find shortest path from root to each node, compare the result of both tree. Obviously, this is not O(n). It has worst case O(nlog(n)).

Yes the order matters...
Fix the first element, take two temp array equal to the size of given aray.

In first array kerp adding elements that are greater than a(0) the first element and similarly keep adding elements lower than a(0) .

What this will do is maintain the order of elemnts on rhs and lhs of root.

Traverse the second array 'b' and check if b(0) = a(0) if they r equal then roots are same and then check if the order of elements of greatr nd smaller elements and the num itself is same.
If same then they make same bst.

Eg.
A is 10,2,4,6,11,12,13
B is 10,11,2,12,13,4,6

Wil give you same bst
Greater elements orderis 11,12,13
Smaller elements order is 2,4,6
Which is same in both arrays.

Time complxis O(n)
Space O(n)

Yes the order matters...
Fix the first element, take two temp array equal to the size of given aray.

In first array kerp adding elements that are greater than a(0) the first element and similarly keep adding elements lower than a(0) .

What this will do is maintain the order of elemnts on rhs and lhs of root.

Traverse the second array 'b' and check if b(0) = a(0) if they r equal then roots are same and then check if the order of elements of greatr nd smaller elements and the num itself is same.
If same then they make same bst.

Eg.
A is 10,2,4,6,11,12,13
B is 10,11,2,12,13,4,6

Wil give you same bst
Greater elements orderis 11,12,13
Smaller elements order is 2,4,6
Which is same in both arrays.

Time complxis O(n)
Space O(n)

For two arrays to generate same BST:

1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))

Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4

(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)

For two arrays to generate same BST:

1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))

Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4

(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)

use 2 variables - l and r. The 'l' variable should always contain the greatest value from the left subtree - Initially, the first element smaller than the root and set another variable lvalue=1. While traversing the array,first compare with the root value, if it is lesser, then if it is lesser than 'l', decrement 'lvalue'. If it is greater, increment 'lvalue' and assign the current value to 'l'.

In the same run if any element is greater than root, compare with 'r' value -if lesser decrement 'rvalue' else increment 'rvalue' and assign 'r' the current element.

Do this for the second array. if the 'rvalue' and 'lvalue' of the two arrays are same, they will have the same structure, else will be different.

Working code for java.
Algorithm as given by words&Lyrics

ackage ds.impl;
import java.util.*;

public class TwoUnsortedArrayBST {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a={6,2,5,1,3,4,7,8,9,10};
		int[] b={6,7,8,9,10,2,5,1,3,4};
		System.out.println("Same BST :"+checkSameBST(a, b));

	}
	
	public static boolean checkSameBST(int[] a , int[] b){
		Queue minA=new LinkedList();
		Queue maxA=new LinkedList();
		Queue minB=new LinkedList();
		Queue maxB=new LinkedList();
		if(a[0]!=b[0]){
		System.out.println("root not same");
			return false;
		}
		else if(a.length!=b.length){
			System.out.println("length not same");
			return false;
		}
			
		else{
			for(int i=1;i<a.length;i++){
				if(a[i]>a[0] && b[i]>b[0] && a[1]!=b[i]){
					System.out.println("maxa and maxb not same");
					return false;
				}
				else{
					maxA.offer(a[i]);
					maxB.offer(b[i]);
				}
				if(a[i]<a[0] && b[i]<b[0] && a[1]!=b[i]){
					System.out.println("mina and minb are not same");
					return false;
				}
				else{
					minA.offer(a[i]);
					minB.offer(b[i]);
				}
					
				if(a[i]>a[0] && b[i]<b[0]){
					if(maxB.isEmpty())
						maxA.offer(a[i]);
					else{
						if((Integer)maxB.peek()==a[i]){
							maxB.remove();
							continue;
						}
						else{
							System.out.println("checking "+(Integer)maxB.peek()+" and "+a[i]);
							return false;
						}
					}
					
					if(minA.isEmpty())
						minB.offer(b[i]);
					else{
						if((Integer)minA.peek()==b[i]){
							minA.remove();
							continue;
						}
						
						else{
							System.out.println("checking "+(Integer)minA.peek()+" and "+b[i]);
							return false;
						}
					}
						
					
				}
				if(a[i]<a[0] && b[i]>b[0]){
					if(maxA.isEmpty())
						maxB.offer(a[i]);
					else{
						if((Integer)maxA.peek()==a[i]){
							maxA.remove();
							continue;
						}
						else{
							System.out.println("checking "+(Integer)maxA.peek()+" and "+a[i]);
							return false;
						}
					}
					
					if(minB.isEmpty())
						minA.offer(b[i]);
					else{
						if((Integer)minB.peek()==b[i]){
							minB.remove();
							continue;
						}
						else{
							System.out.println("checking "+(Integer)minB.peek()+" and "+b[i]);
							return false;
						}
					}
						
					
				}
			}
			return true;
		}
	}

}

BST of given sorted array means it becomes sorted.

Do BFS on both the trees. Improvise BFS to do it in O(n)!!

XOR all of them .. complexity o(n) .. (condition - BST have unique numbers )
if result is 0 - then formed from same array.