---
Difficulty: Medium
Source: 160 Days of Problem Solving
Tags:
- Tree
- Binary Search Tree
---
# π _Day 12. Pair Sum in BST_ π§
The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/tree-gfg-160/problem/find-a-pair-with-given-target-in-bst)
## π‘ **Problem Description:**
Given a **Binary Search Tree (BST)** and a target value, check whether there exists a **pair of nodes** in the BST whose sum equals the given target.
## π **Example Walkthrough:**
### **Example 1:**
#### **Input:**
```
7
/ \
3 8
/ \ \
2 4 9
```
Target = `12`
#### **Output:**
```
True
```
#### **Explanation:**
In the given BST, there exist two nodes **(8 and 4)** that sum up to 12.
### **Example 2:**
#### **Input:**
```
9
/ \
5 10
/ \ \
2 6 12
```
Target = `23`
#### **Output:**
```
False
```
#### **Explanation:**
No pair of nodes in the BST sum up to 23.
### **Constraints:**
- $\(1 \leq \text{Number of Nodes} \leq 10^5\)$
- $\(1 \leq \text{target} \leq 10^6\)$
## π― **My Approach:**
### **Optimized Two-Pointer on Inorder Traversal (`O(N)` Time, `O(N)` Space)**
1. **Convert BST to sorted array** using inorder traversal.
2. **Use two-pointer approach** (left and right) to find the target sum efficiently.
### **Algorithm Steps:**
1. **Perform an inorder traversal** and store the BST elements in a sorted list.
2. Use **two pointers** (`left` at the start, `right` at the end) and check the sum:
- If `arr[left] + arr[right] == target`, return `true`.
- If `arr[left] + arr[right] < target`, move `left++`.
- If `arr[left] + arr[right] > target`, move `right--`.
3. If no such pair exists, return `false`.
## π **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** `O(N)`, since we traverse each node once.
- **Expected Auxiliary Space Complexity:** `O(N)`, due to storing the inorder traversal.
## π **Solution Code**
## Code (C++)
```cpp
class Solution {
public:
bool findTarget(Node* root, int target) {
vector inorder;
function traverse = [&](Node* node) {
if (!node) return;
traverse(node->left);
inorder.push_back(node->data);
traverse(node->right);
};
traverse(root);
int left = 0, right = inorder.size() - 1;
while (left < right) {
int sum = inorder[left] + inorder[right];
if (sum == target) return true;
sum < target ? left++ : right--;
}
return false;
}
};
```
π² Alternative Approaches
## **2οΈβ£ Optimized Hash Set Approach (`O(N)` Time, `O(H)` Space)**
1. **Use DFS to traverse the tree** while maintaining a **hash set** of visited values.
2. **Check if (target - current node value) exists** in the set, if yes, return `true`.
3. **Insert the current node value** into the set and continue.
```cpp
class Solution {
public:
bool findTarget(Node* root, int target) {
unordered_set seen;
return dfs(root, target, seen);
}
bool dfs(Node* root, int target, unordered_set& seen) {
if (!root) return false;
if (seen.count(target - root->data)) return true;
seen.insert(root->data);
return dfs(root->left, target, seen) || dfs(root->right, target, seen);
}
};
```
πΉ **Avoids extra space for storing inorder traversal**
πΉ **Uses Hash Set for `O(1)` lookup**
## **3οΈβ£ BST Iterator + Two-Pointer (`O(N)` Time, `O(H)` Space)**
1. **Use two iterators:** one for **inorder (left to right)** and one for **reverse inorder (right to left)**.
2. **Move iterators towards each other** until the pair is found or iterators cross.
```cpp
class BSTIterator {
stack st;
bool reverse;
public:
BSTIterator(Node* root, bool isReverse) {
reverse = isReverse;
pushAll(root);
}
int next() {
Node* node = st.top(); st.pop();
if (!reverse) pushAll(node->right);
else pushAll(node->left);
return node->data;
}
bool hasNext() { return !st.empty(); }
private:
void pushAll(Node* node) {
while (node) {
st.push(node);
node = reverse ? node->right : node->left;
}
}
};
class Solution {
public:
bool findTarget(Node* root, int target) {
BSTIterator l(root, false), r(root, true);
int i = l.next(), j = r.next();
while (i < j) {
int sum = i + j;
if (sum == target) return true;
sum < target ? i = l.next() : j = r.next();
}
return false;
}
};
```
πΉ **Optimized space using `O(H)` stack instead of `O(N)` vector**
πΉ **Uses BST Iterators for an efficient two-pointer search**
## **Comparison of Approaches**
| **Approach** | β±οΈ **Time Complexity** | ποΈ **Space Complexity** | β‘ **Method** | β
**Pros** | β οΈ **Cons** |
| -------------------------------- | ---------------------- | ----------------------- | ------------- | -------------------------------- | -------------------- |
| **Two-Pointer on Inorder Array** | π’ `O(N)` | π‘ `O(N)` | Two Pointers | Simple and efficient | Extra space for list |
| **Hash Set (DFS)** | π’ `O(N)` | π‘ `O(N)` | Hashing | Faster lookup, no sorting needed | Hashing overhead |
| **BST Iterator (Two-Pointer)** | π‘ `O(N^2)` | π’ `O(H)` | Recursion | No extra storage used | Slow for large BSTs |
---
## π‘ **Best Choice?**
- **For simplicity:** β
**Two-Pointer on Inorder Array** is easiest to understand.
- **For faster lookups:** β
**Hash Set (`O(H)` space)** avoids sorting overhead.
- **For minimal space:** β
**BST Iterator (`O(H)` space, `O(N)` time)** avoids extra space but is slow for large BSTs.
## Code (Java)
```java
class Solution {
public boolean findTarget(Node root, int target) {
List inorder = new ArrayList<>();
inorderTraversal(root, inorder);
int left = 0, right = inorder.size() - 1;
while (left < right) {
int sum = inorder.get(left) + inorder.get(right);
if (sum == target) return true;
if (sum < target) left++;
else right--;
}
return false;
}
private void inorderTraversal(Node node, List inorder) {
if (node == null) return;
inorderTraversal(node.left, inorder);
inorder.add(node.data);
inorderTraversal(node.right, inorder);
}
}
```
## Code (Python)
```python
class Solution:
def findTarget(self, root, target):
inorder = []
def inorderTraversal(node):
if not node:
return
inorderTraversal(node.left)
inorder.append(node.data)
inorderTraversal(node.right)
inorderTraversal(root)
left, right = 0, len(inorder) - 1
while left < right:
total = inorder[left] + inorder[right]
if total == target:
return True
if total < target:
left += 1
else:
right -= 1
return False
```
## π― **Contribution and Support:**
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
---
πVisitor Count
