Skip to main content

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

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

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 kk and return true for any match.

Written by @madhu915
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);
  }
};