Two Sum IV - Input is a BST

Problem

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.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• -105 <= k <= 105

Solution

The problem Two Sum IV - Input is a BST can be solved using an inorder traversal. When a binary search tree is traversed inorder, its elements are sorted in ascending order. Next, we use two pointers to keep track of smallest and biggest numbers in the array that can add up to k.

Implementation

/**
 * Definition for a binary tree node.
 * 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:
    void inorder(TreeNode *root, vector<int> &nums)
    {
        if (root == NULL)
            return;

        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
    bool findTarget(TreeNode *root, int k)
    {
        vector<int> nums;
        inorder(root, nums);

        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            if (nums[left] + nums[right] < k)
                left += 1;
            else if (nums[left] + nums[right] > k)
                right -= 1;
            else
                return true;
        }

        return false;
    }
};