algoadvance

Leetcode 653. Two Sum IV

Problem Statement

Given the root of a Binary Search Tree (BST) and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, otherwise return false.

Clarifying Questions

  1. Do the BST nodes contain only integer values?
    • Yes.
  2. Can the BST contain duplicate values?
    • Typically, BSTs do not contain duplicate values, so we can assume no duplicates unless otherwise specified.
  3. What is the range of values that the BST can contain?
    • The values can be any integers within the range that C++ integers allow.

Strategy

We can leverage the properties of a BST to solve this problem efficiently.

  1. In-Order Traversal: Perform an in-order traversal to get a sorted list of node values.
  2. Two-Pointer Technique: Using the sorted list, apply the two-pointer technique to find if there are two numbers that add up to k.

This approach uses an additional list for storing the BST values, but it allows us to utilize the efficient two-pointer technique to solve the problem in linear time with respect to the number of nodes.

Code

#include <vector>
#include <algorithm>

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 Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        std::vector<int> values;
        
        // In-order traverse to get the sorted values from the BST.
        inOrderTraverse(root, values);
        
        // Apply the two-pointer technique on the sorted values.
        int left = 0;
        int right = values.size() - 1;
        
        while (left < right) {
            int sum = values[left] + values[right];
            if (sum == k) {
                return true;
            } else if (sum < k) {
                left++;
            } else {
                right--;
            }
        }
        
        return false;
    }

private:
    void inOrderTraverse(TreeNode* node, std::vector<int>& values) {
        if (node == nullptr) {
            return;
        }
        
        inOrderTraverse(node->left, values);
        values.push_back(node->val);
        inOrderTraverse(node->right, values);
    }
};

Time Complexity

Overall, the time complexity is O(n). The space complexity is also O(n) due to the additional vector used to store the node values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI