Count Pairs From Two BSTs Whose Sum is Equal to a Given Value

Introduction✈️

Hi Ninja🥷! In this article, we will learn to solve the problem of counting pairs from two BSTs whose sum is equal to a given value. We will use the property of BST that the values of all the nodes in the left subtree of the current node are less than the current node's value and the values of nodes in the right subtree of the current node are greater than the current node's value to solve this problem.

I hope you will enjoy and have fun learning a medium-level DSA problem on binary search tree♟ "Count pairs from two BSTs whose sum is equal to a given value".

Problem Description📔

We have been given two binary search trees and one value. We have to Count pairs from two BSTs whose sum is equal to the given value.

Sample Examples😃

Input:

Output: 

2

Explanation:

Pairs whose sum is equal to the target are: (4,16) and (5,15)

Input:

Output: 

1

Explanation: 

Pair whose sum is equal to the target is: (22,20)

Method 1: Iterative

In this method, we will traverse both the BSTs in an iterative manner from smallest to largest value node.

Algorithm 🤔

• Traverse the first BST from the smallest value node to the node with the largest value. We can achieve this with the help of iterative inorder traversal.
• Traverse the second BST from the largest value node to the smallest value node. We can achieve this with the help of reverse inorder traversal. 
• We will cover these two traversals simultaneously. 
• Then find the sum of the corresponding node's value from both BSTs at a particular instance.
• If the sum is equal to the target, then increase the count. 
• If the target is greater than the sum, then move to the in-order successor of the current node of the first BST.
• Else we move to the in-order predecessor of the current node of the second BST. 
• Perform these steps until any of the two traversals gets completed.

C++ Code

#include <bits/stdc++.h>
using namespace std;


struct Node
{
    int data;
    struct Node *left;
    struct Node *right;


    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};


class Solution
{
public:
    int countPairs(Node* root1, Node* root2, int target)
    {
        if (root1 == NULL || root2 == NULL)
        return 0;
 
        stack<Node*> stk1, stk2;
        Node* top1, *top2;
     
        int count = 0;
 
    // We traverse until either of the two
    // traversals gets completed
    while (true) {
 
        while (root1 != NULL) {
            stk1.push(root1);
            root1 = root1->left;
        }
 
        while (root2 != NULL) {
            stk2.push(root2);
            root2 = root2->right;
        }


        if (stk1.empty() || stk2.empty())
            break;
 
        top1 = stk1.top();
        top2 = stk2.top();
 
        // if the sum == target
        if ((top1->data + top2->data) == target) {
            // increment the count
            count++;


            stk1.pop();
            stk2.pop();
 
            root1 = top1->right;
            root2 = top2->left;
        }


        else if ((top1->data + top2->data) < target) {
            stk1.pop();
            root1 = top1->right;
        }
        else {
            stk2.pop();
            root2 = top2->left;
        }
    }
 
    return count;


    }
};



//{ Driver Code Starts.


int main()
{
    //BST 1
    Node* root1 = new Node(10); 
    root1->left = new Node(5); 
    root1->right = new Node(20); 
    root1->left->left = new Node(4); 
    root1->left->right = new Node(7); 
    root1->right->left = new Node(14);
    root1->right->right = new Node(22);
 
    //BST 2
    Node* root2 = new Node(15);
    root2->left = new Node(12); 
    root2->right = new Node(18);
    root2->left->left = new Node(3); 
    root2->left->right = new Node(14); 
    root2->right->left = new Node(16);
    root2->right->right = new Node(20);
    
    int target = 20;
        Solution ob;
        cout << ob.countPairs(root1, root2, target);
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Output: 

2

Complexity Analysis

Time Complexity: O(n1 + n2), where n1 and n2 are the numbers of nodes in the first  and second BST, respectively.

Space Complexity: O(h1 + h2), Where h1 is the height of the first BST and h2 is the height of the second BST.

Also check out - Inorder Predecessor