Given a binary search tree, and an integer X, the task is to check if there exists a pair of distinct nodes in BST with sum equal to X. If yes then print Yes else print No.
Examples:
Input: X = 5
5
/ \
3 7
/ \ / \
2 4 6 8
Output: Yes
2 + 3 = 5. Thus, the answer is "Yes"
Input: X = 10
1
\
2
\
3
\
4
\
5
Output: No
Approach: We have already discussed a hash based approach in this article. The space complexity of this is O(N) where N is the number of nodes in BST.
In this article, we will solve the same problem using a space efficient method by reducing the space complexity to O(H) where H is the height of BST. For that, we will use two pointer technique on BST. Thus, we will maintain a forward and a backward iterator that will iterate the BST in the order of in-order and reverse in-order traversal respectively. Following are the steps to solve the problem:
- Create a forward and backward iterator for BST. 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 < x, we will make forward iterator point to the next element.
- If v1 + v2 > x, we will make backward iterator point to the previous element.
- If we find no such pair, answer will be “No”.
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 to find a pair with given sumbool existsPair(node* root, int x){ // Iterators for BST stack<node *> it1, it2; // Initializing forward iterator node* c = root; while (c != NULL) it1.push(c), c = c->left; // Initializing backward iterator c = root; while (c != NULL) it2.push(c), c = c->right; // Two pointer technique while (it1.top() != it2.top()) { // Variables to store values at // it1 and it2 int v1 = it1.top()->data, v2 = it2.top()->data; // Base case if (v1 + v2 == x) return true; // Moving forward pointer if (v1 + v2 < x) { c = it1.top()->right; it1.pop(); while (c != NULL) it1.push(c), c = c->left; } // Moving backward pointer else { c = it2.top()->left; it2.pop(); while (c != NULL) it2.push(c), c = c->right; } } // Case when no pair is found return false;}// Driver codeint main(){ node* root = new node(5); root->left = new node(3); root->right = new node(7); root->left->left = new node(2); root->left->right = new node(4); root->right->left = new node(6); root->right->right = new node(8); int x = 5; // Calling required function if (existsPair(root, 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 to find a pair with given sumstatic boolean existsPair(node root, int x){ // Iterators for BST Stack<node > it1 = new Stack<node>(), it2 = new Stack<node>(); // Initializing forward iterator node c = root; while (c != null) { it1.push(c); c = c.left; } // Initializing backward iterator c = root; while (c != null) { it2.push(c); c = c.right; } // Two pointer technique while (it1.peek() != it2.peek()) { // Variables to store values at // it1 and it2 int v1 = it1.peek().data, v2 = it2.peek().data; // Base case if (v1 + v2 == x) return true; // Moving forward pointer if (v1 + v2 < x) { c = it1.peek().right; it1.pop(); while (c != null) { it1.push(c); c = c.left; } } // Moving backward pointer else { c = it2.peek().left; it2.pop(); while (c != null) { it2.push(c); c = c.right; } } } // Case when no pair is found return false;}// Driver codepublic static void main(String[] args){ node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); int x = 5; // Calling required function if (existsPair(root, x)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by 29AjayKumar |
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, 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 = root1 while (c != None): it2.append(c) c = c.right # Two pointer technique while (it1[-1] != it2[-1]): # To store the value of the nodes # current iterators are pointing to v1 = it1[-1].data v2 = it2[-1].data # Base case 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__': 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 = 5 # Calling required function if (existsPair(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 to find a pair with given sumstatic bool existsPair(node root, int x){ // Iterators for BST Stack<node > it1 = new Stack<node>(), it2 = new Stack<node>(); // Initializing forward iterator node c = root; while (c != null) { it1.Push(c); c = c.left; } // Initializing backward iterator c = root; while (c != null) { it2.Push(c); c = c.right; } // Two pointer technique while (it1.Peek() != it2.Peek()) { // Variables to store values at // it1 and it2 int v1 = it1.Peek().data, v2 = it2.Peek().data; // Base case if (v1 + v2 == x) return true; // Moving forward pointer if (v1 + v2 < x) { c = it1.Peek().right; it1.Pop(); while (c != null) { it1.Push(c); c = c.left; } } // Moving backward pointer else { c = it2.Peek().left; it2.Pop(); while (c != null) { it2.Push(c); c = c.right; } } } // Case when no pair is found return false;}// Driver codepublic static void Main(String[] args){ node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); int x = 5; // Calling required function if (existsPair(root, x)) Console.Write("Yes"); else Console.Write("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 = this.right = null; }}// Function to find a pair with given sumfunction existsPair(root, x){ // Iterators for BST let it1 = [], it2 = []; // Initializing forward iterator let c = root; while (c != null) { it1.push(c); c = c.left; } // Initializing backward iterator c = root; while (c != null) { it2.push(c); c = c.right; } // Two pointer technique while (it1[it1.length-1] != it2[it2.length-1]) { // Variables to store values at // it1 and it2 let v1 = it1[it1.length - 1].data, v2 = it2[it2.length - 1].data; // Base case if (v1 + v2 == x) return true; // Moving forward pointer if (v1 + v2 < x) { c = it1[it1.length - 1].right; it1.pop(); while (c != null) { it1.push(c); c = c.left; } } // Moving backward pointer else { c = it2[it2.length - 1].left; it2.pop(); while (c != null) { it2.push(c); c = c.right; } } } // Case when no pair is found return false;}// Driver codelet root = new node(5);root.left = new node(3);root.right = new node(7);root.left.left = new node(2);root.left.right = new node(4);root.right.left = new node(6);root.right.right = new node(8);let x = 5;// Calling required functionif (existsPair(root, x)) document.write("Yes");else document.write("No");// This code is contributed by unknown2108</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!
