CareerCup

Divide the elements(except the root) of each array into two sets-one that contains the elements that come in the left sub-tree in the order in which they occur in the array and the other that contains the elements that come in the right sub-tree again in the order in which they occur in the array.
Make left and right arrays for both the arrays. Then the left arrays of both as well as the right arrays of both should be exactly same.
For example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
left1 : 5
right1 : 20 15 30
left2 : 5
right2 : 20 15 30
therefore the arrays would produce the same BSTs

But for:
Array1:10 5 20 15 30
Array2:10 15 20 30 5
left1 : 5
right1 : 20 15 30
left2 : 5
right2 : 15 20 30
As right1 and right2 are not same, therefore different BSTs are produced.
Here is the code:

#include<stdio.h>
#define SIZE 1000

int checkMakeSameTree(int A[],int B[],int n)
{
    int root;
    int left[SIZE];
    int right[SIZE];
    int i,j,k;
    int leftsize = 0;
    int rightsize = 0;
    if(A[0] == B[0])
        root = A[0];
    else
        return 0;
    for(i=1;i<n;i++)
    {
        if(A[i] > root)
            right[rightsize++] = A[i];
        else
            left[leftsize++] = A[i];
    }
    j=k=0;
    for(i=1;i<n;i++)
    {
        if(B[i] > root)
        {
            if(k < rightsize && right[k] == B[i])
                k++;
            else
                return 0;
        }
        else
        {
            if(j < leftsize && left[j] == B[i])
                j++;
            else
                return 0;
        }
    }
    if(j == leftsize && k == rightsize)
        return 1;
    else
        return 0;
}

How BST is represented by array? Preorder?

after you create the BST for both the sequences .. one option is we need to find out the INORDER,PREORDER or POSTORDER traversal , and compare them for the 2 BST's that you get from the given sequence .. exact replica of BST should have same in,pre,post order sequences .

Create BST with one array. For second array using insert / traverse function check second array element is matching with the stored data.

@vipul
The above suggest method doesnot work for the following condition
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13

A left : 3,6,1,4,7
A right : 10,14,13

b left : 3,6,4,1 ,7
B right : 10,14,13

A left != B left
according to condition this should not for BST
which is wrong

It's simple and can be done in O(n).

Create from first array a BST say aBST..
Once done when you are trying to create second BST, say bBST compare the value of the node (being inserted) with the aBST current node value, if equal insert it and move down else return false and you are done.

i thot of a similar approach but with a twist:

1. Create a BST with first input list say aBST, but each node should have an extra bool variable (say IsReached) set to false.

2. Now, start with the first element in second input list. The first element has to be the same as the root node of aBST, (otherwise we are done already), mark it as IsReached = true and goto step 3.

3. for each subsequent element in second input list, do a search in aBST. But condition is that you can test search only till the immediate children of any node where IsReached = true. If found, set the isReached flag = 1 & move on. Otherwise conclude & exit.

howzat?

One Approach is Pretty Clear by creating BST O(nlogn) then checking two tree for identical O(N) overall O(nlogn) ..i wonder if there exist O(N) Time & O(1) Space also without extra space .??

Build Two separate BST and Do the level Order traversal on both.If Two sequence wants to generate similar tree then Level Order traversal must be same. Correct if I am wrong?As I am beginner thats why not thinking much about space and time complexity.

This will do

static boolean preorder(Node r1, Node r2){

if( r1.l == null && r1.r == null && r2.l == null && r2.r == null)
return r1.d == r2.d;
else if(
(r1.l == null && r2.l != null) || (r1.r == null && r2.r != null) ||
(r1.l != null && r2.l == null) || (r1.r != null && r2.r == null ))
return false;
else
return preorder(r1.l, r2.l) && r1.d == r2.d && preorder(r1.r, r2.r);
}

what about this

for (int i = 0; i < length - 1; i++)
{
if (arr1[i] < arr1[i+1] && arr2[i] < arr2[i+1])
return false;
if (arr1[i] > arr1[i+1] && arr2[i] > arr2[i+1])
return false;
}

return true;

take first element as pivot of the quick sort.
for both the arrays position this element such that left elements are all smaller and right elements are all bigger.
Now compare the array: if they are equal then same BST else not.

eg:
1) Array1:10 5 20 15 30
Array2:10 20 15 30 5

after processing
Array1: 5 10 20 15 30
Array2: 5 10 20 15 30
Result: True


Array1:10 5 20 15 30
Array2:10 15 20 30 5
after processing
Array1: 5 10 20 15 30
Array1: 5 10 15 20 30
Result: false


Comments people. If this approach is correct

I think We can do it by using the array splitting in two part. one is smaller then first nbr and one is bigger the first nbr and seq should not be break for ex: (first element is common as it is root so ignore it)
array A = 57926813
then make two array from it 213 and 7968
Array B = 52713968
then make two array from it 213 and 7968
here both array are same so tree should be ideantical..

If any one of the following conditions are false, then the BSTs are not identical else they are identical.

1: The first element of both arrays are same.
2: The relative ordering of all elements greater than the first element(root) is same in both the arrays.
3: The relative ordering of all elements lesser than the first element(root) is same in both the arrays.

Time Complexity O(n)
Space Complexity O(1)

For the two arrays to give same BST, the two arrays should contain the same elements. (much like anagrams).
sort the two and compare O(n lg n)
I hope their is a better solution to check for anagrams..