Print all pairs from two BSTs whose sum is greater than the given value

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction

This blog will discuss the solution to the problem to print all pairs from two BSTs whose sum is greater than the given value where we are given two binary search trees, and we have to print all the pairs whose sum is greater than X. To understand  the problem better, look at the example given below:

 Bst 1:    

   

  Bst 2:   

 

  X = 18

Output: 

The pairs are: 

{10, 10}

{10, 13}

{10, 12}

{10, 15}

{7, 13}

{7, 12}

{7, 15}

{6, 13}

{6, 15}

{5, 13}

{5, 15}

Brute force Approach

To solve this problem, print all pairs from two BSTs whose sum is greater than the given value, we will traverse the first bst, and for every node in the first bst with value Y, we will check if a node with a value greater than (X - Y) is present in the other bst or not. If it is present, then we will print that pair. 

Algorithm

  1. Create two binary search trees and pass their heads in one function named printPairs().
  2. Do preorder traversal for the first tree, and every node of the first tree check for pairs in the second tree by doing preorder in the second tree.
  3. If there is a pair where the sum of nodes of both the trees is greater than x, print the pair.
  4. After that, make two recursive calls, one for the second binary search tree's left side and another for the second binary search tree, and another for the right side of the second binary search tree.
  5. Now all the pairs will be printed one by one. 

Code in C++

// C++ implementation to print all pairs from two BSTs whose sum is greater than the given value
#include <bits/stdc++.h>
using namespace std;

// Structure of each node of BST
struct node
{
    int key;
    struct node *left, *right;
};

// Function to create a new BST node
node *TreeNode(int data)
{
    node *temp = new node();
    temp->key = data;
    temp->left = temp->right = NULL;
    return temp;
}

// function to insert node in bst
struct node *insert(struct node *node,
                    int key)
{
    // If the tree is empty, then return a new node
    if (node == NULL)
        return TreeNode(key);

    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left,key);
    else if (key > node->key)
        node->right = insert(node->right,key);

    // Return the (unchanged) node pointer
    return node;
}
void findPair(node *root1, node *root2, int x)
{
    // base case
    if (!root2)
        return;
    // following preorder root --> left --> right    
    // check if the current node values of both the trees is greater than x or not    
    if (root1->key + root2->key > x)
    {
        // if greater then print the pair
        cout << root1->key << " " << root2->key << endl;
    }
    // make recusive call to left side of second tree when it is not null
    findPair(root1, root2->left, x);
    // make recusive call to right side of second tree when it is not null
    findPair(root1, root2->right, x);
    return;
}
void printPairs(node *root1, node *root2, int x)
{
    // base case
    if (!root1)
        return;
    // following preorder root --> left --> right    
    // check for pairs with current node of first tree  
    findPair(root1, root2, x);
    // make recursive call to the left side of first tree when it is not null
    printPairs(root1->left, root2, x);
    // make recursive call to the right side of first tree when it is not null
    printPairs(root1->right, root2, x);
    return;
}
int main()
{

    /* Formation of BST 1
            5
            / \
          3   7
          /\   /\
        2  4 6  8
    */

    struct node *root1 = NULL;
    root1 = insert(root1, 5);
    insert(root1, 3);
    insert(root1, 2);
    insert(root1, 4);
    insert(root1, 7);
    insert(root1, 6);
    insert(root1, 8);

    /* Formation of BST 2
            4
            / \
          2   6
          /\   /\
        1  3 5  7
    */

    struct node *root2 = NULL;
    root2 = insert(root2, 4);
    insert(root2, 2);
    insert(root2, 1);
    insert(root2, 3);
    insert(root2, 6);
    insert(root2, 5);
    insert(root2, 7);

    int x = 10;

    // Print pairs
    printPairs(root1, root2, x);

    return 0;
}

 

Output:

5 6
5 7
4 7
7 4
7 6
7 5
7 7
6 6
6 5
6 7
8 4
8 3
8 6
8 5
8 7

Complexity Analysis

Time Complexity: O(n1*h2)

Here n1 is the number of nodes in the first bst, and h2 is the height of the second tree, and since we are traversing the second tree for every node of the first tree, the time complexity is O(n1*h2).

Space Complexity: O(1)

Since no extra space is used, the space complexity will be O(1).

Optimized Approach

In this approach, we will first traverse the first bst from the smallest node value to the largest node value, and this can be done using inorder traversal, and we will store this in an array named inorderBst1. After that, we will traverse the second bst from the largest node value to the smallest node value, and this can also be done using inorder traversal, and we will store this in another array named inorderBst2. We will take the sum of the node values from both the BST's simultaneously and traverse in both the arrays. In the first array, we will traverse using index i, and in the other array, we will traverse using index j. Now, sum = inorderBst1[i] + inorderBst2[j]. If sum > x, we will print the pair and decrement the index value j; otherwise, we will increment the index value i. 

Algorithm

  1. We will first traverse bst one from smallest value node to largest value node, and we will store this inorder traversal in the array named inorderBst1 with an index called i.
  2. We will traverse through the bst two from largest value node to smallest value node, and we will store this inorder traversal in an array named inorderBst2 with index named j.
  3. Now we will sum the corresponding node's value from both the Bsts and check if the sum is greater than x or not.
  4. If it is greater than x, we will print the pair and decrement the index j by one else; we will increment the index i by 1.

Code in C++

// C++ implementation to print all pairs from two BSTs whose sum is greater than the given value
#include <bits/stdc++.h>
using namespace std;

// structure of each node of BST
struct node
{
    int key;
    struct node *left, *right;
};

// function to create a new BST node
node *TreeNode(int data)
{
    node *temp = new node();
    temp->key = data;
    temp->left = temp->right = NULL;
    return temp;
}

// function to insert node in bst
struct node *insert(struct node *node, int key)
{
    // if the tree is empty, then return a new node
    if (node == NULL)
        return TreeNode(key);

    // otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    // return the (unchanged) node pointer
    return node;
}

// to get the size of the tree
int sizeOfTree(node *root)
{
    if (root == NULL)
    {
        return 0;
    }

    // recursive call to store the left side size of the bst
    int left = sizeOfTree(root->left);

    // recusive call to store the right side size of the bst
    int right = sizeOfTree(root->right);

   // recursive call to store the total size
    return (left + right + 1);
}

// function to store the inorder of the bst
void storeInorder(node *root, int inOrder[], int &index)
{
    // Base condition
    if (root == NULL)
    {
        return;
    }

    // left recursive call
    storeInorder(root->left, inOrder, index);

    // to store the elements in the array
    inOrder[index++] = root->key;

    // right recursive call
    storeInorder(root->right, inOrder, index);
}

// function to print the pairs
void print(int inOrder[], int i, int index, int value)
{
    while (i < index)
    {
        cout << "{" << inOrder[i] << ", " << value << "}" << endl;
        i++;
    }
}

// to check a valid pair and to print it
void printPairs(int inOrderBst1[], int inOrderBst2[], int index, int j, int x)
{
    int i = 0;

    while (i < index && j >= 0)
    {

        if (inOrderBst1[i] + inOrderBst2[j] > x)
        {
            print(inOrderBst1, i, index, inOrderBst2[j]);
            j--;
        }
        else
        {
            i++;
        }
    }
}

// function to generate all the pairs and to print valid pairs
void checkPairs(node *root1, node *root2, int k)
{
    // storing the size of first bst
    int sizeOfBst = sizeOfTree(root1);

    // to store the inorder of first bst
    int inOrderBst1[sizeOfBst + 1];
    int index1 = 0;

    // storing the size of second bst
    sizeOfBst = sizeOfTree(root2);

    // to store the inorder of second bst
    int inOrderBst2[sizeOfBst + 1];
    int index2 = 0;

    // to store the inorder the first bst
    storeInorder(root1, inOrderBst1, index1);

    // to store the inorder the second bst
    storeInorder(root2, inOrderBst2, index2);

    // to print the pair
    printPairs(inOrderBst1, inOrderBst2, index1, index2 - 1, k);
}
int main()
{

    /* Formation of BST 1
            5
            / \
          3   7
          /\   /\
        2  4 6  8
    */

    struct node *root1 = NULL;
    root1 = insert(root1, 5);
    insert(root1, 3);
    insert(root1, 2);
    insert(root1, 4);
    insert(root1, 7);
    insert(root1, 6);
    insert(root1, 8);

    /* Formation of BST 2
            10
            /  \
          8   12
          /\   /\
        6  9 11 13
    */

    struct node *root2 = NULL;
    root2 = insert(root2, 10);
    insert(root2, 8);
    insert(root2, 6);
    insert(root2, 9);
    insert(root2, 12);
    insert(root2, 11);
    insert(root2, 13);

    int x = 18;

    // print pairs
    checkPairs(root1, root2, x);

    return 0;
}

 

Output: 

{6, 13}
{7, 13}
{8, 13}
{7, 12}
{8, 12}
{8, 11}

Complexity Analysis

Time Complexity: O(n1+n2)

The time complexity is O(n1+n2).

Space Complexity: O(n1 + n2)

Since we have made two arrays to store both the bst’s, the space complexity will be O(1).

Frequently asked questions

Q1. What is a binary tree?

Ans. A binary tree is a data structure in programming languages to represent the hierarchy.  Each node of the binary tree can have either 0,1, or 2 children.

 

Q2. What are leave nodes in a tree?

Ans. Leave nodes of a tree are those nodes that don’t have any children, and both the pointers of the nodes point to null.

 

Q3. What is a binary search tree?

Ans. A binary search tree is a sorted binary tree in which all the nodes of the binary tree have a value greater than their left child node and a value smaller than their right child node.

Key takeaways

In this article, we discussed the problem print all pairs from two BSTs whose sum is greater than the given value. We have discussed its two approaches: the brute force approach and the optimized approach, which is more efficient than the brute force approach in both the time and the space complexity. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

 

You can learn more about binary search trees hereUntil then, Keep Learning and Keep Coding and practicing on Code studio.


Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think