DAY 66 - Two Sum IV - Input is a BST

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

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

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

 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

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: