Two Sum in BST

#include <bits/stdc++.h> // Includes common standard libraries (iostream, vector, etc.)
#include "BST.h"         // Assumed to contain Node class, insertIntoBST, takeinput, levelOrderTraversal

using namespace std;     // Use the standard namespace

// Note: The Node class, insertIntoBST, takeinput, and levelOrderTraversal
// are assumed to be defined in "BST.h".
/*
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) { ... }
};

Node* insertIntoBST(Node* root, int data) { ... }
void takeinput(Node* &root) { ... }
void levelOrderTraversal(Node* root) { ... }
*/

// Helper function: Performs an in-order traversal of the BST
// and stores all node data into the 'ans' vector in sorted order.
// Time Complexity: O(N)
// Space Complexity: O(H) for recursion stack
void inOrder(Node* root, vector<int>& ans) {
    // Base case: if node is NULL, return
    if(root == NULL) {
        return;
    }

    // Traverse left subtree
    inOrder(root->left, ans);
    // Process current node: add its data to the vector
    ans.push_back(root->data);
    // Traverse right subtree
    inOrder(root->right, ans);
}

// Function to check if a pair with the given 'target' sum exists in the BST.
// Approach: Convert BST to sorted array, then use Two-Pointer technique.
// Time Complexity: O(N) (O(N) for traversal + O(N) for two-pointer scan)
// Space Complexity: O(N) (for storing elements in vector)
bool checkTwoSum(Node* root, int target) {
    // If the BST is empty, no pair can be found.
    if(root == NULL) {
        return false;
    }

    // Step 1: Convert the BST into a sorted vector using in-order traversal.
    vector<int> arr;
    inOrder(root, arr); // arr now contains elements in ascending order

    // Step 2: Use the Two-Pointer technique on the sorted vector.
    int i = 0;             // Pointer for the start of the array (smallest elements)
    int j = arr.size() - 1; // Pointer for the end of the array (largest elements)

    // Loop while the left pointer is less than the right pointer.
    // (i < j ensures we are checking distinct elements)
    while(i < j) {
        int currentSum = arr[i] + arr[j]; // Calculate current sum

        if(currentSum == target) {
            return true; // Found a pair that sums to target
        }

        if(currentSum > target) {
            // If sum is too large, decrement right pointer to try a smaller element.
            j--;
        } else { // currentSum < target
            // If sum is too small, increment left pointer to try a larger element.
            i++;
        }
    }

    // If the loop finishes, no pair was found.
    return false;
}

int main() {
    Node* root = NULL; // Initialize root of the BST
    int target;        // The target sum to find

    cout << "Enter data to create BST : ";
    takeinput(root); // Build the BST

    cout << "Enter the target value : ";
    cin >> target; // Get the target sum from the user

    cout << endl << "Level Order Traversal : " << endl;
    levelOrderTraversal(root); // Print the tree structure (optional, for verification)

    // Check if a pair with the target sum exists
    bool isSumPresent = checkTwoSum(root, target);

    // Print the result
    if(isSumPresent) {
        cout << "Sum pair is present in BST!" << endl;
    } else {
        cout << "Sum pair is not present in BST!" << endl;
    }

    return 0;
}

/*
Example Input for tree creation:
14 12 28 8 4 10 9 11 19 32 18 17 22 21 24 39 -1

Corresponding sorted array (from in-order traversal):
[4, 8, 9, 10, 11, 12, 14, 17, 18, 19, 21, 22, 24, 28, 32, 39]

Example Scenarios:
1. Enter target value : 30
   Expected: 10 + 20 (no 20), 12 + 18, 9 + 21, 8 + 22, 4 + 26 (no 26).
   Let's check 12 + 18 = 30. Yes, this pair exists.
   Output: Sum pair is present in BST!

2. Enter target value : 50
   Expected: 12 + 38 (no 38), 14 + 36 (no 36), 18 + 32, 19 + 31 (no 31), 22 + 28, 24 + 26 (no 26).
   Pairs: 18 + 32 = 50. 22 + 28 = 50. Yes.
   Output: Sum pair is present in BST!

3. Enter target value : 100
   Expected: No pair. Max sum 32 + 39 = 71.
   Output: Sum pair is not present in BST!

4. Enter target value : 1 (target too small)
   Output: Sum pair is not present in BST!
*/

1. Binary Search Tree (BST) Recap

• A Binary Search Tree (BST) ensures that all nodes in its left subtree are smaller than the root, and all nodes in its right subtree are larger.
• Key Insight: An In-order traversal of a BST visits nodes in strictly ascending order. This property is vital for the solution.

2. Two Sum Problem

• The classic “Two Sum” problem asks to find if there exist two elements in a collection that sum up to a specific target value.
• For a sorted array, the Two-Pointer technique is highly efficient for this problem.

3. Supporting Components (Briefly)

• Node class: Defines the structure of a BST node (data, left, right).
• insertIntoBST, takeinput, levelOrderTraversal: Functions (assumed in BST.h) to build and visualize the tree.

4. inOrder(Node* root, vector<int>& ans) Function

• Purpose: Performs a standard in-order traversal on the BST to collect all node data into a vector<int>.
• Logic:
  1. Base Case: If root is NULL, return (end of a branch).
  2. Left Subtree: Recursively call inOrder on root->left.
  3. Process Node: Add root->data to the ans vector.
  4. Right Subtree: Recursively call inOrder on root->right.
• Result: After the call finishes, the ans vector will contain all BST node values in sorted (ascending) order.

5. checkTwoSum(Node* root, int target) Function

• Purpose: Determines if there are two distinct nodes in the BST whose data values sum up to the target.

• Core Idea:

  1. Convert the BST into a sorted array (or vector) using in-order traversal.
  2. Apply the efficient Two-Pointer technique on this sorted array.

• Logic Flow:

  1. Handle Empty Tree: If root is NULL, return false (no nodes to form a sum).
  2. Build Sorted Array: Create an empty vector<int> arr; and call inOrder(root, arr); to populate it.
  3. Two-Pointer Technique:
     • Initialize i = 0 (pointer at the beginning of arr) and j = arr.size() - 1 (pointer at the end of arr).
     • Start a while loop: while(i < j). (Using i < j ensures distinct elements are used for the sum. If a node could sum with itself, i <= j would be used, but generally, “two sum” implies distinct elements/indices).
     • Calculate currentSum = arr[i] + arr[j].
     • If currentSum == target: A pair is found. Return true.
     • If currentSum > target: The sum is too large. To decrease the sum, move the right pointer left: j--.
     • If currentSum < target: The sum is too small. To increase the sum, move the left pointer right: i++.
  4. If the loop completes without finding a pair, return false.

6. Complexity Analysis

• Time Complexity: O(N)
  • O(N) for the inOrder traversal to convert the BST into a sorted array, where N is the number of nodes.
  • O(N) for the two-pointer scan on the array (at most N iterations).
  • Total: O(N) + O(N) = O(N).
• Space Complexity: O(N)
  • O(N) for storing the BST elements in the vector<int> arr.
  • O(H) for the recursion stack of inOrder traversal, where H is the height of the tree. O(H) is at most O(N) in the worst case.
  • Total: Dominated by the vector storage, so O(N).

---