Problem Description

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

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

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

Examples

Example 1
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Explanation: (5, 4), (3, 6) and (2, 7)
       5
     /   \
    3     6
  /  \     \
2     4     7

Example 2
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
Explanation: None of pair sums up to 28.
       5
     /   \
    3     6
  /  \     \
2     4     7

How to Solve

Although the given tree is the binary search tree (BST), its property doesn’t help to find the answer. A pair of two numbers can be found anywhere, not always from top to bottom. Because of this, every tree node should be checked like a binary tree.

The solution here uses the breadth-first search. While traversing the tree, (k - node value)s are saved in the set. If the current node’s value is in the set, the combination is found.

Solution

• C++
• Java
• JavaScript
• Python
• Ruby

• /**
   * 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 TwoSum4BST {
  public:
      bool findTarget(TreeNode* root, int k) {
          if (!root) {
              return false;
          }
          queue<TreeNode*> q({root});
          set<int> seen;
          while (!q.empty()) {
              TreeNode* cur = q.front();
              q.pop();
              if (seen.find(cur->val) != seen.end()) {
                  return true;
              }
              seen.insert(k - cur->val);
              if (cur->left) {
                  q.push(cur->left);
              }
              if (cur->right) {
                  q.push(cur->right);
              }
          }
          return false;
      }
  };
  

• # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class TwoSum4BST:
      def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
          if not root:
              return False
          seen, queue = set(), [root]
          while queue:
              cur = queue.pop(0)
              if cur.val in seen:
                  return True
              seen.add(k - cur.val)
              if cur.left:
                  queue.append(cur.left)
              if cur.right:
                  queue.append(cur.right)
          return False
  

Complexities

• Time: O(n)
• Space: O(n)