###
[Amazon Interview] Compare the BSTs

Given two unsorted integer arrays, your task is to compare the BST formed by both the arrays.

e.g [3 2 1 4 5] & [3 4 2 5 1]
when the BST is formed by taking the elements from the left, both BST turn out to be same.

3
/ \
2 4
/ \
1 5

Expected time complexity O(n).

**Approach:**
First observation is that the first element of the array forms the root of the BST.
So the first element needs to be equal of both the arrays.
Now the next left element which gets added to the BST is the next smaller element in the array, and same is true for the next right element in the BST.

So the sequence of the elements of the less than the the first element should be same in both arrays

And the same is true for the elements greater than the root element

So if the first array contains elements {9, 14, 8, 11, 4, 7, 15, 10, 6}
so any array which forms the same BST should have the elements of the sort
{9, ., 14, ..,11, .., 15, .., 10} & {9, .., 8, .., 4, .., 7, .., 6}

Both the preconditions can be verified trivially by two scans over the arrays.

Check if length of both arrays is same.

ReplyDeleteCheck if root of both tree is same .

Partion the two arrays making root element i.e.array[0] as pivot.

Now recursively check for left and right subtree.

We can use stable partitioning technique of Quicksort.

Thanx

Please check http://codepad.org/xmVfyVIK

In the above approach, we can use same arrays for keeping the partition elements

ReplyDeleteSpace Complexity - O(1)

Worst case time complexity - O(n^2), if arrays make skewed BST.

@Navin ...

ReplyDeletethe average case O(nlogn) and worst case O(n^2) can be achieved naively by creating both the BST and comparing.

Try something else to reach a worst case time complexity of O(n)

#include

ReplyDeleteint Same_BST(int* arr1,int* arr2,int len1,int len2)

{

int i=0,j=0;

if(len1!=len2)//check length is same

return 0;

if(arr1[i]!=arr2[j])//root is same

return 0;

while(iroot) are same

{

if(arr1[i]>arr1[0])

{

while(arr2[j++]!=arr2[i]);

if(j>len2)

return 0;

}

i++;

}

i=0;

j=0;

while(ilen2)

return 0;

}

i++;

}

return 1;

}

#include

ReplyDeleteint Same_BST(int* arr1,int* arr2,int len1,int len2)

{

int i=0,j=0;

if(len1!=len2)//check length is same

return 0;

if(arr1[i]!=arr2[j])//root is same

return 0;

while(iarr1[0])

{

while(arr2[j++]!=arr2[i]);

if(j>len2)

return 0;

}

i++;

}

i=0;

j=0;

while(ilen2)

return 0;

}

i++;

}

return 1;

}

I m trying to paste my code and it is not getting paste correctly.

ReplyDelete@ashish can u explain ur logic.

ReplyDelete@aviral

ReplyDeletelet's take this eg:

e.g [3 2 1 5 6 4] & [3 5 2 4 1 6]

Your logic doesn't hold good. Correct me if i am wrong.

boolean check(int a[],int b[])

ReplyDelete{

int less1[],less2[],grt1[],grt2[];

if(a[0]!=b[0] || a.length != b.length) return false;

for(int i=1,j=k=m=n=0,i<n;i++)

{

if(a[i]<a[0])

{ less1[j] = a[i]; j++; }

else { grt1[k] = a[i]; k++; }

if(b[i]<b[o])

{ less2[m] = b[i]; m++; }

else { grt2[n] = b[i]; n++; }

}

if(less1[] == less2[] && grt1[] == grt2[])

return true;

else return false;

}

If the breadth first traversal of the trees match then they are identical.

ReplyDelete