Two Sum IV – Input is a BST (Two Pointer Approach)

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:

1. If sum == target -> return true
2. If sum < target -> move left++
3. 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.