This content originally appeared on DEV Community and was authored by Nithya Dharshini official
We already know the classic Two Sum problem on arrays.
But what if the data is inside a Binary Search Tree (BST)?
At first, it looks tricky… but we can convert it into something familiar.
Key Idea
A BST inorder traversal gives a sorted array.Once we have a sorted array, we can apply:
-> Two Pointer Technique
Approach
Step 1: Convert BST → Sorted Array
Use inorder traversal
Left → Root → Right
This guarantees sorted order.
Step 2: Apply Two Pointers
left = 0 , right = n - 1
Then:
- If sum == target -> return true
- If sum < target -> move left++
- If sum > target -> move right--
Why This Works
BST property -> inorder gives sorted values
Sorted values -> perfect for two pointer optimization
So we reduce:
Tree problem -> Array problem
Code (C++)
class Solution {
public:
void inorder(TreeNode* root, vector<int>& arr) {
if (root == NULL) return;
inorder(root->left, arr);
arr.push_back(root->val);
inorder(root->right, arr);
}
bool findTarget(TreeNode* root, int k) {
vector<int> arr;
inorder(root, arr);
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == k) return true;
else if (sum > k) right--;
else left++;
}
return false;
}
};
Example
Input:
root = [5,3,6,2,4,null,7]
k = 9
Sorted array:
[2, 3, 4, 5, 6, 7]
Check pairs:
2 + 7 = 9
Complexity
Time: O(n)
Space: O(n) (for array)
What I Learned
- Tree problems can be simplified using traversal
- Converting to array helps reuse known patterns
- Two pointer works beautifully on sorted data
Final Thought
Sometimes the best trick is:
-> Convert the problem into something you already know
Tree -> Array
Array -> Two Pointer
Done.
This content originally appeared on DEV Community and was authored by Nithya Dharshini official
Nithya Dharshini official | Sciencx (2026-03-19T15:47:10+00:00) Two Sum IV – Input is a BST (Two Pointer Approach). Retrieved from https://www.scien.cx/2026/03/19/two-sum-iv-input-is-a-bst-two-pointer-approach/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.