Skip to content

653. Two Sum IV Input Is A Bst

Hash Table Two Pointers Tree Depth-First Search Breadth-First Search Binary Search Tree Binary Tree

Problem - Two Sum IV Input Is A Bst

Easy

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, 104].
  • -104 <= Node.val <= 104
  • root is guaranteed to be a valid binary search tree.
  • -105 <= k <= 105

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        # visited = set()

        # def dfs(root) -> bool:
        #     if root is None:
        #         return False
        #     if k - root.val in visited:
        #         return True
        #     visited.add(root.val)

        #     return dfs(root.left) or dfs(root.right)

        # return dfs(root)

        visited = set()
        queue = deque([root])
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if k - node.val in visited:
                    return True
                visited.add(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return False

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 19.6 MB (91.58%)