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 otherwise false.

Examples

Example 1:

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

Explanation : The BST contains multiple pair of nodes that sum up to k.
3 + 6 => 9.
5 + 4 => 9.
2 + 7 => 9.

Example 2:

Input : root = [5, 3, 6, 2, 4, null, 7] , k = 14

Output : false

Explanation : There is no pair in given BST that sum up to k.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

An inorder traversal of a Binary Search Tree (BST) results in a sorted list of elements. This sorted nature can be utilized to find a pair of elements that add up to a specified sum (K). By applying the Two Sum technique to this sorted list, the solution becomes straightforward. Two pointers are set at the beginning and the end of the list. Their positions are adjusted based on whether their combined value is less than, greater than, or equal to the target sum.

Approach:

1. Execute an inorder traversal of the BST to generate a sorted list of elements. This traversal follows the pattern: left subtree -> root -> right subtree.
2. With the sorted list in hand, set one pointer at the start (left end) and another at the end (right end) of the list.
3. Adjust the pointers as follows:
   1. If the sum of the values at the pointers is less than the target, move the left pointer to the right (towards larger values).
   2. If the sum is greater than the target, move the right pointer to the left (towards smaller values).
   3. If the sum equals the target, return the pair of values.

Code:

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
public:
    bool twoSumBST(TreeNode* root, int k) {
        // Get sorted list of elements from BST
        vector<int> sorted_elements = inorderTraversal(root);

        // Initialize two pointers
        int left = 0, right = sorted_elements.size() - 1;

        // Use two pointers to find if there is a pair with sum k
        while (left < right) {
            int current_sum = sorted_elements[left] + sorted_elements[right];
            if (current_sum == k) {
                return true;
            } else if (current_sum < k) {
                left++;
            } else {
                right--;
            }
        }

        return false;
    }

private:
    // Helper function to perform inorder traversal and get sorted elements
    vector<int> inorderTraversal(TreeNode* node) {
        vector<int> elements;
        inorderHelper(node, elements);
        return elements;
    }

    // Recursive helper to fill elements during inorder traversal
    void inorderHelper(TreeNode* node, vector<int>& elements) {
        if (!node) return;
        inorderHelper(node->left, elements);
        elements.push_back(node->data);
        inorderHelper(node->right, elements);
    }
};

// Main method to test the solution
int main() {
    // Example tree: [5, 3, 6, 2, 4, nullptr, 7]
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    int k = 9;
    Solution solution;
    bool result = solution.twoSumBST(root, k);
    cout << (result ? "True" : "False") << endl;  // Output: True

    // Clean up memory
    delete root->right->right;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), The time complexity is linear because we are traversing the entire binary search tree once to get the sorted elements, and then we are using two pointers to find the pair that sums to k, which also takes linear time.
• Space Complexity:O(N), The space complexity is linear because we are storing the sorted elements in an array, which takes linear space.

2️⃣ Optimal Approach

Intuition:

While a previous method used O(N) space complexity by storing the inorder traversal, this can be avoided by directly utilizing the properties of a Binary Search Tree (BST). Understanding the BST Iterator is crucial for this approach. The BSTIterator class provides functionality to access the next and previous elements in the BST. By initializing pointers 'i' and 'j' to the first and last elements of the inorder traversal using this class, the pointers can be moved through the tree using next() for larger values and before() for smaller values. This method efficiently navigates the BST to find the pair of elements that sum to the target value without needing additional storage for the traversal.

Approach:

1. Initialize pointers 'i' and 'j' to the first and last elements of the BST's inorder traversal using the BSTIterator class.
2. Use the next() function to move pointer 'i' to larger values and the before() function to move pointer 'j' to smaller values within the BST.
3. Adjust the pointers based on their sum:
   1. If the sum of the values at the pointers is less than the target, increment pointer 'i' to move towards larger values.
   2. If the sum is greater than the target, decrement pointer 'j' to move towards smaller values.
   3. If the sum equals the target, return true.

Code:

#include <bits/stdc++.h>
using namespace std;

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

// BST Iterator to iterate in the inorder and reverse inorder manner
class BSTIterator {
    stack<TreeNode*> st;
    bool reverse;
    
    // Helper function to push all left or right nodes
    void pushAll(TreeNode* node) {
        while (node != nullptr) {
            st.push(node);
            node = (reverse) ? node->right : node->left;
        }
    }
    
public:
    BSTIterator(TreeNode* root, bool isReverse) : reverse(isReverse) {
        pushAll(root);
    }
    
    // Check if there are more elements in the BST
    bool hasNext() {
        return !st.empty();
    }
    
    // Get the next element in the inorder or reverse inorder traversal
    int next() {
        TreeNode* node = st.top();
        st.pop();
        if (!reverse) pushAll(node->right);
        else pushAll(node->left);
        return node->data;
    }
};

class Solution {
public:
    bool twoSumBST(TreeNode* root, int k) {
        if (!root) return false;
        
        // Initialize two iterators
        BSTIterator l(root, false); // normal inorder
        BSTIterator r(root, true);  // reverse inorder
        
        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;
    }
};

int main() {
    // Create the tree
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    // Create solution instance
    Solution solution;
    int k = 9;
    
    // Check if there exist two elements in the BST such that their sum is equal to k
    bool result = solution.twoSumBST(root, k);
    cout << (result ? "True" : "False") << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), the code iterates over the BST once to initialize the iterators, and then iterates over the BST again to find the two sum, where N is the number of nodes in the BST.
• Space Complexity:O(N), the code uses two iterators, each of which stores at most N nodes in the stack, to iterate over the BST.