Sunday, January 5, 2014

Finding out if given arrays represent identical binary search tree (BST)

You are given two arrays of integers. You need to check if the binary search tree is generated out of two arrays considering first element as root, then will the trees be identical. You are not allowed to create the binary tree. 

The techniques is fairly simple. Just try to identify from root, left and right elements of every sub tree. E.g. in the array 5, 6, 3, 7, 2 
Root: 5 -> Left 3
Root: 5 -> Right 6 -> right 7
Root: 3 -> left 2
Root: 6 -> right 7

Follow this for both the arrays and check if the left and right element of every sub tree are in the same order if not both array can not generate the identical BST.

Code below demonstrate this technique.  


bool DoesGivenArraysRepresentIdenticalBST( vector<int> firstArray, vector<int> secondArray)
{
    if( firstArray.count() != secondArray.count() )
        return false;

    if( firstArray.size() <= 0)
        return true;

    //Check if the root of every sub tree is same
    if( firstArray[0] != secondArray[0] )
        return false;

    if( firstArray.size() <= 1)
        return true;

    vector<int> left1;
    vector<int> right1;

    for(int i = 1; i < firstArray.size(); i++)
    {
        if( firstArray[0] < firstArray[i] )
            right1.Add(firstArray[i]);
        else
            left1.Add(firstArray[i]);
    }

    vector<int> left2;
    vector<int> right2;

    for(int i = 1; i < secondArray.size(); i++)
    {
        if( secondArray[0] < secondArray[i] )
            right2.Add(secondArray[i]);
        else
            left2.Add(secondArray[i]);
    }

    return DoesGivenArraysRepresentIdenticalBST( left1, left2 ) && DoesGivenArraysRepresentIdenticalBST( right1, right2 );
}

No comments:

Post a Comment