Given two Binary search trees and an integer X, the task is to find a pair of nodes, one belonging to the first BST and the second belonging to other such that their sum is equal to X. If there exists such a pair, print Yes else print No.
Examples:
Input: X = 100
BST 1:
5
/ \
3 7
/ \ / \
2 4 6 8
BST 2:
11
\
13
Output: No
There is no such pair with given value.
Input: X = 16
BST 1:
5
/ \
3 7
/ \ / \
2 4 6 8
BST 2:
11
\
13
Output: Yes
5 + 11 = 16
Approach: We will solve this problem using two pointer approach.
We will create a forward iterator on the first BST and backward on the second. Thus, we will maintain forward and a backward iterator that will iterate the BSTs in the order of in-order and reverse in-order traversal respectively.
- Create a forward and backward iterator for first and second BST respectively. Let’s say the value of nodes they are pointing at are v1 and v2.
- Now at each step,
- If v1 + v2 = X, we found a pair.
- If v1 + v2 less than or equal to x, we will make forward iterator point to the next element.
- If v1 + v2 greater than x, we will make backward iterator point to the previous element.
- We will continue the above while both iterators are pointing to a valid node.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node of the binary treestruct node { int data; node* left; node* right; node(int data) { this->data = data; left = NULL; right = NULL; }};// Function that returns true if a pair// with given sum exists in the given BSTsbool existsPair(node* root1, node* root2, int x){ // Stack to store nodes for forward and backward // iterator stack<node *> it1, it2; // Initializing forward iterator node* c = root1; while (c != NULL) it1.push(c), c = c->left; // Initializing backward iterator c = root2; while (c != NULL) it2.push(c), c = c->right; // Two pointer technique while (it1.size() and it2.size()) { // To store the value of the nodes // current iterators are pointing to int v1 = it1.top()->data, v2 = it2.top()->data; // If found a valid pair if (v1 + v2 == x) return true; // Moving forward iterator if (v1 + v2 < x) { c = it1.top()->right; it1.pop(); while (c != NULL) it1.push(c), c = c->left; } // Moving backward iterator else { c = it2.top()->left; it2.pop(); while (c != NULL) it2.push(c), c = c->right; } } // If no such pair found return false;}// Driver codeint main(){ // First BST node* root1 = new node(11); root1->right = new node(15); // Second BST node* root2 = new node(5); root2->left = new node(3); root2->right = new node(7); root2->left->left = new node(2); root2->left->right = new node(4); root2->right->left = new node(6); root2->right->right = new node(8); int x = 23; if (existsPair(root1, root2, x)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Node of the binary treestatic class node { int data; node left; node right; node(int data) { this.data = data; left = null; right = null; }};// Function that returns true if a pair// with given sum exists in the given BSTsstatic boolean existsPair(node root1, node root2, int x){ // Stack to store nodes for forward and backward // iterator Stack<node> it1 = new Stack(), it2 = new Stack(); // Initializing forward iterator node c = root1; while (c != null) { it1.push(c); c = c.left; } // Initializing backward iterator c = root2; while (c != null) { it2.push(c); c = c.right; } // Two pointer technique while (it1.size() > 0 && it2.size() > 0) { // To store the value of the nodes // current iterators are pointing to int v1 = it1.peek().data, v2 = it2.peek().data; // If found a valid pair if (v1 + v2 == x) return true; // Moving forward iterator if (v1 + v2 < x) { c = it1.peek().right; it1.pop(); while (c != null) { it1.push(c); c = c.left; } } // Moving backward iterator else { c = it2.peek().left; it2.pop(); while (c != null) { it2.push(c); c = c.right; } } } // If no such pair found return false;}// Driver codepublic static void main(String[] args) { // First BST node root1 = new node(11); root1.right = new node(15); // Second BST node root2 = new node(5); root2.left = new node(3); root2.right = new node(7); root2.left.left = new node(2); root2.left.right = new node(4); root2.right.left = new node(6); root2.right.right = new node(8); int x = 23; if (existsPair(root1, root2, x)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach# Node of the binary treeclass node: def __init__ (self, key): self.data = key self.left = None self.right = None# Function that returns true if a pair# with given sum exists in the given BSTsdef existsPair(root1, root2, x): # Stack to store nodes for forward # and backward iterator it1, it2 = [], [] # Initializing forward iterator c = root1 while (c != None): it1.append(c) c = c.left # Initializing backward iterator c = root2 while (c != None): it2.append(c) c = c.right # Two pointer technique while (len(it1) > 0 and len(it2) > 0): # To store the value of the nodes # current iterators are pointing to v1 = it1[-1].data v2 = it2[-1].data # If found a valid pair if (v1 + v2 == x): return True # Moving forward iterator if (v1 + v2 < x): c = it1[-1].right del it1[-1] while (c != None): it1.append(c) c = c.left # Moving backward iterator else: c = it2[-1].left del it2[-1] while (c != None): it2.append(c) c = c.right # If no such pair found return False# Driver codeif __name__ == '__main__': # First BST root1 = node(11) root1.right = node(15) # Second BST root2 = node(5) root2.left = node(3) root2.right = node(7) root2.left.left = node(2) root2.left.right = node(4) root2.right.left = node(6) root2.right.right = node(8) x = 23 if (existsPair(root1, root2, x)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG {// Node of the binary treepublic class node { public int data; public node left; public node right; public node(int data) { this.data = data; left = null; right = null; }};// Function that returns true if a pair// with given sum exists in the given BSTsstatic bool existsPair(node root1, node root2, int x){ // Stack to store nodes for forward and backward // iterator Stack<node> it1 = new Stack<node>(), it2 = new Stack<node>(); // Initializing forward iterator node c = root1; while (c != null) { it1.Push(c); c = c.left; } // Initializing backward iterator c = root2; while (c != null) { it2.Push(c); c = c.right; } // Two pointer technique while (it1.Count > 0 && it2.Count > 0) { // To store the value of the nodes // current iterators are pointing to int v1 = it1.Peek().data, v2 = it2.Peek().data; // If found a valid pair if (v1 + v2 == x) return true; // Moving forward iterator if (v1 + v2 < x) { c = it1.Peek().right; it1.Pop(); while (c != null) { it1.Push(c); c = c.left; } } // Moving backward iterator else { c = it2.Peek().left; it2.Pop(); while (c != null) { it2.Push(c); c = c.right; } } } // If no such pair found return false;}// Driver codepublic static void Main(String[] args) { // First BST node root1 = new node(11); root1.right = new node(15); // Second BST node root2 = new node(5); root2.left = new node(3); root2.right = new node(7); root2.left.left = new node(2); root2.left.right = new node(4); root2.right.left = new node(6); root2.right.right = new node(8); int x = 23; if (existsPair(root1, root2, x)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Node of the binary treeclass node{ constructor(data) { this.data = data; this.left = null; this.right = null; }}// Function that returns true if a pair// with given sum exists in the given BSTsfunction existsPair(root1,root2,x){ // Stack to store nodes for forward and backward // iterator let it1 =[], it2 = []; // Initializing forward iterator let c = root1; while (c != null) { it1.push(c); c = c.left; } // Initializing backward iterator c = root2; while (c != null) { it2.push(c); c = c.right; } // Two pointer technique while (it1.length > 0 && it2.length > 0) { // To store the value of the nodes // current iterators are pointing to let v1 = it1[it1.length-1].data, v2 = it2[it2.length-1].data; // If found a valid pair if (v1 + v2 == x) return true; // Moving forward iterator if (v1 + v2 < x) { c = it1[it1.length-1].right; it1.pop(); while (c != null) { it1.push(c); c = c.left; } } // Moving backward iterator else { c = it2[it2.length-1].left; it2.pop(); while (c != null) { it2.push(c); c = c.right; } } } // If no such pair found return false;}// Driver code// First BST let root1 = new node(11); root1.right = new node(15); // Second BST let root2 = new node(5); root2.left = new node(3); root2.right = new node(7); root2.left.left = new node(2); root2.left.right = new node(4); root2.right.left = new node(6); root2.right.right = new node(8); let x = 23; if (existsPair(root1, root2, x)) document.write("Yes"); else document.write("No"); // This code is contributed by patel2127</script> |
Output:
Yes
Time complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
