Skip to main content

Two Sum in Binary Search Tree

Problem Statement:​

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

  • Example:

✅ Solution: Two Sum IV – Input is a BST (Two Approaches)​

Approach 1: Two Pointers Using BST Iterator​

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class BSTIterator {
public:
    stack<TreeNode*> st;
    bool rev = false;  // false: in-order, true: reverse in-order

    BSTIterator(TreeNode *root, bool isReverse) {
        rev = isReverse;
        pushAll(root);
    }

    int next() {
        TreeNode *node = st.top();
        st.pop();
        if (!rev) pushAll(node->right); // in-order: right next
        else pushAll(node->left);       // reverse in-order: left next
        return node->val;
    }

private:
    void pushAll(TreeNode *node) {
        while (node != NULL) {
            st.push(node);
            if (!rev) node = node->left;
            else node = node->right;
        }
    }
};

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;
        BSTIterator l(root, false);
        BSTIterator r(root, true);

        int i = l.next();
        int j = r.next();

        while (i < j) {
            if (i + j == k) return true;
            else if (i + j < k) i = l.next();
            else j = r.next();
        }
        return false;
    }
};

Approach 2: DFS + Hash Set​

class Solution {
public:
    bool helper(TreeNode *root, int k, unordered_set<int> &seen) {
        if (root == NULL) return false;
        if (seen.count(k - root->val)) return true;
        seen.insert(root->val);
        return helper(root->left, k, seen) || helper(root->right, k, seen);
    }

    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> seen;
        return helper(root, k, seen);
    }
};

📝 Notes for Both Approaches​

✅ How It Works​

  • BST Iterator Two Pointer:
    • Uses two custom iterators: one from smallest, one from largest.
    • Combines in-order and reverse in-order traversal like two pointers on a sorted array.
    • Saves space compared to storing a full array.
  • DFS + Hash Set:
    • Traverses the BST in DFS style.
    • Uses a hash set to check if k - current_value exists.
    • Simpler logic but uses O(N) space.

🧩 Key Formula​

  • BST Iterator:

    Two Pointer logic → i + j == k

  • DFS + Set:

    Check → k - root->val ∈ seen

⏱️ Time & Space Complexity​

ApproachTimeSpace
BST IteratorO(N)O(h)
DFS + Hash SetO(N)O(N)
  • N = total nodes, h = height of BST.

⚠️ Edge Cases​

  • Empty tree → return false.
  • Single node → false.
  • Duplicate node values (though BST usually has unique values).

💡 Other Approaches​

  • Store full in-order traversal in an array and apply the two-pointer technique: O(N) space.
  • Morris Traversal for O(1) space (advanced, rarely required in interviews).

🔁 Related Problems​

  • LeetCode 653. Two Sum IV – Input is a BST
  • LeetCode 1. Two Sum
  • LeetCode 167. Two Sum II – Input Array is Sorted
  • LeetCode 173. BST Iterator

✅ Real-Life Analogy​

  • BST Iterator Approach: Like reading from both ends of a sorted list, one person starts from the beginning and one from the end, both moving toward the middle.
  • DFS + Set Approach: Like remembering all past values you've seen while searching for a pair.
💬

Discussion & Doubts