0653 - Two Sum IV - Input is a BST (Easy)

Problem Link

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Problem Statement

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

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Constraints:

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

Approach 1: Depth First Search

Perform a depth first search in the binary search tree to search for the node with the target value. The values of the nodes are added to the hashset recursively as the tree is travelled in a DFS fashion and the node with the target value is searched within the hashset for each recursive call. The left subtree is traversed followed by the right subtree in order to determine the pair of nodes with sum $k$ and return true for any match.

class Solution {
public:
  // set keeps track of the corresponding values of nodes traversed in a DFS fashion
  unordered_set<int> node;

  bool findTarget(TreeNode* root, int k) {
    // DFS approach
    if (!root) return false;
    // if the target pair is found, then return true
    if (node.find(k - root->val) != node.end()) return true;
    // add node value to hashset
    node.insert(root->val);
    // search left and right subtrees
    return findTarget(root->left, k) || findTarget(root->right, k);
  }
};