Two Sum Iv Input Is A Bst - Leetcode Solution

Problem Statement:

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

Example:

Input: 5 /
3 6 / \
2 4 7

Target = 9

Output: True

Solution Approach:

The following solution approaches are possible for this problem:

I. Inorder Traversal + Two Pointers

The Idea behind this approach is to create an array by traversing the tree inorderly, and then check with two pointers, if there are two values that make up the target.

Algorithm:

1. Create an empty array to store the inorder traversal of BST.
2. Traverse the BST inorderly and insert each element into the array.
3. Initialize two pointers left and right at the start and end of the array, respectively.
4. While left < right: a. Calculate sum of the left and right pointers' values. b. If the sum is equal to target, return True. c. If the sum is less than target, increment left. d. If the sum is greater than target, decrement right.
5. Return False if no pair found.

Time Complexity: O(N), where N is the number of nodes in the BST. Space Complexity: O(N), where N is the number of nodes in the BST.

Python Code:

class Solution: def findTarget(self, root: TreeNode, k: int) -> bool:

    res = []
    self.inorder(root,res)
    
    left, right = 0, len(res)-1
    
    while left < right:
        cur_sum = res[left] + res[right]
        if cur_sum == k:
            return True
        elif cur_sum < k:
            left += 1
        else:
            right -= 1
            
    return False
    
def inorder(self, root, res):
    if not root:
        return
    self.inorder(root.left,res)
    res.append(root.val)
    self.inorder(root.right,res)

II. HashSet

The Idea behind this approach is to use set data structure to check if the target - current node's value exists in the tree or not.

Algorithm:

1. Traverse the tree recursively and at each node, check if (target - node value) is in the set.
2. If it is, return True.
3. If it is not, add the current node's value to the set.
4. Recursively check if the target exists in left subtree.
5. Recursively check if the target exists on the right subtree.
6. Return False if no pair is found.

Time Complexity: O(N), where N is the number of nodes in the BST. Space Complexity: O(N), where N is the number of nodes in the BST.

Python Code:

class Solution: def findTarget(self, root: TreeNode, k: int) -> bool:

    self.visited = set()
    
    return self.helper(root, k)
    
    
def helper(self, root, k):
    if not root:
        return False
    
    if k - root.val in self.visited:
        return True
    
    self.visited.add(root.val)
    
    return self.helper(root.left, k) or self.helper(root.right, k)

1