Introduction
In Computer Science, a binary tree is a non-linear hierarchical data structure made up of nodes linked together. The first node is known as the root, and each node can have up to two child nodes — one on the left and one on the right.
In this blog, we will discuss one of the problems of Binary Search Trees which is mostly asked in interviews and coding competitions. Let’s start going!
Problem Statement
In this problem, we are given a sum as input and two BSTs also, and we have to find the two node pair elements whose key value sum is equal to the given sum lie in Binary Search Trees (BSTs).
Let’s understand the problem pair with a given sum such that pair elements lie in different Binary Search Trees ( BSTs) with some examples.
Sample Examples
Example 1:
Input:
sum = 10
Output:
(3, 7)
(5, 5)
(7, 3)
Explanation: We will store the node of each tree in a separate vector while traversing. If the present node has a node in another vector for which the sum of both nodes is equal to the target node, then we will return the pair.
Example 2:
Input:
sum = 30
Output:
(12, 18)
(17, 13)
Explanation: We will store the node of each tree in a separate vector while traversing. If the present node has a node in another vector for which the sum of both nodes is equal to the target node, then we will return the pair.
Approach to find Pair with given sum
The best solution to find the Pair with the given sum is first to store the inorder traversal of both the binary tree in a separate array and then use a two-pointer approach to check for the Pair whose sum is equal to the target sum.
Algorithm to find Pair with given sum
🔑 First, take an input element in two binary search trees.
🔑 Calculate the in-order traversal of both the binary search trees.
🔑 Store the in-order traversal of binary search trees in two arrays.
🔑 Initialize a left variable pointing to the left of array a1.
🔑 Initialize a right variable pointing to the right of array a2.
🔑 If a1[left] > a2[right], then decrement the right variable in backward direction.
🔑 If a1[left] < a2[right], then increment the left variable in forward direction.
🔑 If a1[left]== a2[right], then returns the Pair equal to the target, and increment the left and decrement the right variable to find the next Pair if possible.
Implementation
Java Program to find Pair with given sum such that Pair elements lie in different BSTs.
import java.util.*;
class Coding_Ninjas
{
static class Node
{
int key;
Node left, right;
};
static Node New_Node(int n)
{
Node t = new Node();
t.key = n;
t.left = t.right = null;
return t;
}
static Node insert_Element(Node root, int data)
{
if (root == null)
return New_Node(data);
if (root.key > data)
root.left = insert_Element(root.left, data);
else
root.right = insert_Element(root.right, data);
return root;
}
static void storeInorder(Node p, ArrayList<Integer> a)
{
if (p==null)
{
return;
}
storeInorder(p.left, a);
a.add(p.key);
storeInorder(p.right, a);
}
static void pair(ArrayList<Integer> a1, ArrayList<Integer> a2, int s)
{
int l = 0;
int r = a2.size() - 1;
while (l < a1.size() && r >= 0)
{
if (a1.get(l) + a2.get(r) == s)
{
System.out.println( "(" +a1.get(l) + ", "+ a2.get(r) + ") ");
l++;
r--;
}
else if (a1.get(l) + a2.get(r) < s)
{
l++;
}
else
{
r--;
}
}
}
static void pairSum(Node root1, Node root2, int s)
{
ArrayList<Integer> a1= new ArrayList<Integer>();
ArrayList<Integer> a2 = new ArrayList<Integer>();
storeInorder(root1, a1);
storeInorder(root2, a2);
pair(a1, a2, s);
}
public static void main(String args[])
{
Node root1 = null;
Node root2 = null;
root1 = insert_Element(root1, 5);
root1 = insert_Element(root1, 3);
root1 = insert_Element(root1, 8);
root1 = insert_Element(root1, 1);
root1 = insert_Element(root1, 6);
root1 = insert_Element(root1, 7);
root1 = insert_Element(root1, 12);
root2 = insert_Element(root2, 8);
root2 = insert_Element(root2, 5);
root2 = insert_Element(root2, 10);
root2 = insert_Element(root2, 3);
root2 = insert_Element(root2, 6);
root2 = insert_Element(root2, 7);
root2 = insert_Element(root2, 12);
int s = 10;
pairSum(root1, root2, s);
}
}
Output:
(3, 7)
(5, 5)
(7, 3)
C++ Program to find Pair with given sum such that Pair elements lie in different BSTs.
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
struct Node* New_Node(int num)
{
struct Node* temp = new Node;
temp->key = num;
temp->left = temp->right = NULL;
return temp;
}
Node* insert_Element(Node* root, int key)
{
if (root == NULL)
return New_Node(key);
if (root->key > key)
root->left = insert_Element(root->left, key);
else
root->right = insert_Element(root->right, key);
return root;
}
void storeInorder(Node *p, vector<int> &v)
{
if (p==NULL)
{
return;
}
storeInorder(p->left, v);
v.push_back(p->key);
storeInorder(p->right, v);
}
void pair_s(vector<int> &v1, vector<int> &v2, int s)
{
int l = 0;
int r = v2.size() - 1;
while (l< v1.size() && r >= 0)
{
if (v1[l] + v2[r] == s)
{
cout << "(" << v1[l] << ", "<< v2[r] << ")"<<endl;
l++;
r--;
}
else if (v1[l] + v2[r] < s)
{
l++;
}
else
{
r--;
}
}
}
void pair_Sum(Node *root1, Node *root2, int s)
{
vector<int> v1, v2;
storeInorder(root1, v1);
storeInorder(root2, v2);
pair_s(v1, v2, s);
}
int main()
{
struct Node* root1 = NULL;
struct Node* root2 = NULL;
root1 = insert_Element(root1, 12);
root1 = insert_Element(root1, 10);
root1 = insert_Element(root1, 15);
root1 = insert_Element(root1, 5);
root1 = insert_Element(root1, 13);
root1 = insert_Element(root1, 7);
root1 = insert_Element(root1, 17);
root2 = insert_Element(root2, 14);
root2 = insert_Element(root2, 11);
root2 = insert_Element(root2, 18);
root2 = insert_Element(root2, 8);
root2 = insert_Element(root2, 13);
root2 = insert_Element(root2, 16);
root2 = insert_Element(root2, 21);
int s = 30;
pair_Sum(root1, root2, s);
return 0;
}
Output:
(12, 18)
(17, 13)
Time Complexity
The time complexity of the above approach for the problem of finding Pair with a given sum such that Pair elements lie in different BSTs is O(n) as we are using two pointer approach whose time complexity is O(n).
Space Complexity
The space complexity of the above approach for the problem of finding Pair with a given sum such that Pair elements lie in different BSTs is O(n) as we are storing the nodes in two vectors.
85+ registered