Two Sum IV - Input is a BST (Leet Code-653)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 226. This is a Leet code problem named Two Sum IV – Input is a BST. We will solve it using python and it is the best space and time-optimized solution.

Question of Two Sum IV - Input is a BST

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.

If you’re given a binary search tree and a goal sum, find the two numbers in the tree such that they add up to the target sum. It’s reasonable to suppose that each input has precisely one answer. You can’t use the same element again, either. You may return the answers in any order you like.

Example

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⁴].
-10⁴ <= Node.val <= 10⁴
root is guaranteed to be a valid binary search tree.
-10⁵ <= k <= 10⁵

Approach to solve Two Sum IV - Input is a BST

To solve this problem first we will declare two variables first one is a queue to store children of the visited nodes and after that, we visit the stored nodes. The second variable is to store the value of the visited node. While traversing through the tree we just check whether the difference of the node value and the target value is in variable 2 or not. If it is present then we return true.

Algorithm

This method performs the following steps for a given input binary search tree:

k is the target value.
Check base condition i.e. if the node is node then return False.
Create variable bfs to store elements of the tree.
Create variable s to store the value of the visited node.
Repeat steps 5 to 8 for each value of bfs.
if value of k-i is found in s then return true and break for loop.
Otherwise, add the current node value in s.
Add left and right child to bfs.
End For loop
Return False

Python Code for Two Sum IV - Input is a BST


# 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:

        #base case
        if not root:
            return False
        #to store elements of tree
        bfs = [root]
        #to store the value of visited nodes
        s = set()
        #for loop to traverse in tree
        for i in bfs:
            #if value of k-i is found in s then return true
            
            if k - i.val in s: 
                return True
            #add current node value in s 
            s.add(i.val)
            #add left and right child to bfs
            if i.left: bfs.append(i.left)
            if i.right: bfs.append(i.right)

        return False

Python Code Recursive Approach


# 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:
            seen = []   
        
        def traversal(node):
            if not node:
                return False
            #we find difference and check it is in seen or not 
            if k - node.val in seen:
                #if find then return true
                return True
            #otherwise add it in seen
            seen.append(node.val)
            #traverse in left and right direction 
            return traversal(node.left) or traversal(node.right)
        
        return traversal(root)