Find pairs with given sum such that pair elements lie in different BSTs - GeeksforGeeks

Find pairs with given sum such that pair elements lie in different BSTs - GeeksforGeeks
Given two Binary Search Trees (BST) and a given sum. The task is to find pairs with given sum such that each pair elements must lie in different BST.

An efficient solution for this solution is to store Inorder traversals of both BSTs in two different auxiliary arrays vect1[] and vect2[]. Now we follow method1 of this article. Since Inorder traversal of BST is always gives sorted sequence, we don not need to sort our arrays.

• Take iterator left and points it to the left corner vect1[].
• Take iterator right and points it to the right corner vect2[].
• Now if vect11[left] + vect2[right] < sum then move left iterator in vect1[] in forward direction i.e; left++.
• Now if vect1[left] + vect2[right] > sum then move right iterator in vect[] in backward direction i.e; right–.

void pairSumUtil(vector<int> &vect1, vector<int> &vect2,

                                                int sum)

{

    // Initialize two indexes to two different corners

    // of two vectors.

    int left = 0;

    int right = vect2.size() - 1;

 

    // find pair by moving two corners.

    while (left < vect1.size() && right >= 0)

    {

        // If we found a pair

        if (vect1[left] + vect2[right] == sum)

        {

            cout << "(" << vect1[left] << ", "

                 << vect2[right] << "), ";

            left++;

            right--;

        }

 

        // If sum is more, move to higher value in

        // first vector.

        else if (vect1[left] + vect2[right] < sum)

            left++;

 

        // If sum is less, move to lower value in

        // second vector.

        else

            right--;

    }

}

 

// Prints all pairs with given "sum" such that one

// element of pair is in tree with root1 and other

// node is in tree with root2.

void pairSum(Node *root1, Node *root2, int sum)

{

    // Store inorder traversals of two BSTs in two

    // vectors.

    vector<int> vect1, vect2;

    storeInorder(root1, vect1);

    storeInorder(root2, vect2);

 

    // Now the problem reduces to finding a pair

    // with given sum such that one element is in

    // vect1 and other is in vect2.

    pairSumUtil(vect1, vect2, sum);

}

We have another space optimized approach to solve this problem. The idea is to convert bst into doubly linked list and apply above method for doubly linked list.See this article.

Time complexity : O(n)
Auxiliary Space : O(1)

Read full article from Find pairs with given sum such that pair elements lie in different BSTs - GeeksforGeeks