DAY 66 - Two Sum IV - Input is a BST
Tags: leetcode, algorithms, coding, tutorial
Published: 2023-08-08 18:02:33

Hi Guys! Nayan this side and welcome to 66'th day of 100DaysOfCode Challenge. I guess we are 2/3rd done as of  this article.
Let's get to today's question. We are going to solve another Binary Search Tree Question.


## Question : [_Two Sum IV - Input is a BST_](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/)

_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:_

> ![Example 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6af3l8e2e9vtt2cgmorj.png)
> **Input:** root = [5,3,6,2,4,null,7], k = 9
> **Output:** true

---


## Intuition:
### Brute Force Approach:
- I don't think the question needs any understanding. We have implemented two sum before, the change instead of an array we are given a Binary Search Tree.
- If we had an array we could solve this problem right?. Let's do that then. Using the property of BST that it's inorder traversal gives us the sorted elements of that tree , we can form an array of inorder traversal and perform regular two sum on that.
- Since the array is sorted we don't need to maintain a hash map for this approach, we can simply use a two pointer approach to get the answer.

---

### Optimised Solution:
- In the previous thought process we took O(N) time because we visited every element and O(N) space for storing them.
- Since this is a bst, surely we can solve this more optimized.(in most cases we can).
- So while traversing we do a regular two sum and put our values of the root into the hashMap.
- If that hashmap contains the difference element(like regular two sum). We return true, otherwise we go for left and right subtrees.

---

## Algorithm & Code:

### Algorithm: Optimized
The algorithm uses a recursive approach to traverse the BST and efficiently find two distinct nodes with values that sum up to the target. Here's how the provided code works:

1. **`helper` Function:**
   The `helper` function is a recursive function that traverses the BST while maintaining a hash map to track the encountered values.
   - If the `root` node is `NULL`, the function returns `false`, as there are no nodes left to explore.
   - If the difference between the target value and the current node's value (`k - root->val`) is present in the hash map, it means we have found two distinct nodes with the desired sum, and the function returns `true`.
   - The current node's value is added to the hash map to mark its presence.
   - The function then recursively checks the left and right subtrees using `helper(root->left, k)` and `helper(root->right, k)`.
   - The `|` operator is used to combine the results of the left and right subtree checks. If either subtree contains the desired sum, the overall result will be `true`.

2. **`findTarget` Function:**
   The `findTarget` function acts as a wrapper function that calls the `helper` function to find the desired sum.
   - It returns the result of the `helper(root, k)` call.

---

### Code: Optimized

```cpp
 unordered_map<int, int> hash;
    bool helper(TreeNode* root, int k){
        if(root == NULL) return false;
        if(hash.count(k-root->val)) return true;
        hash[root->val]++;
        return helper(root->left, k) | helper(root->right, k);
    }
    bool findTarget(TreeNode* root, int k) {
        return helper(root, k);
    }

```

---

### Code: Brute Force

```cpp
void solve(TreeNode* root, vector<int> & inorder){
        if(root==NULL)
            return ;
            // LNR
        solve(root->left,inorder);
        inorder.push_back(root->val);
        solve(root->right,inorder);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> inorder;
        solve(root,inorder);
        int s=0,e=inorder.size()-1;
        int sum=0;
        while(s<e)
        {
            sum=inorder[s]+inorder[e];
            if(sum==k)
                return true;
            else if (sum>k)
                e--;
            else
                s++;
        }
        return false;
    }

```

### Complexity Analysis:

| Aspect                   | Hash Map Approach | Two Pointers Approach |
|--------------------------|-------------------|-----------------------|
| Time Complexity          | O(n)              | O(n)                  |
| Space Complexity         | O(h) or O(n)      | O(n)                  |
| Memory Efficiency        | Good              | Moderate                  |