Similar Problems
Similar Problems not available
Two Sum Iv Input Is A Bst - Leetcode Solution
Companies:
LeetCode: Two Sum Iv Input Is A Bst Leetcode Solution
Difficulty: Easy
Topics: binary-search-tree hash-table depth-first-search breadth-first-search two-pointers tree binary-tree
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:
- Create an empty array to store the inorder traversal of BST.
- Traverse the BST inorderly and insert each element into the array.
- Initialize two pointers left and right at the start and end of the array, respectively.
- 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.
- 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:
- Traverse the tree recursively and at each node, check if (target - node value) is in the set.
- If it is, return True.
- If it is not, add the current node's value to the set.
- Recursively check if the target exists in left subtree.
- Recursively check if the target exists on the right subtree.
- 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)
Two Sum Iv Input Is A Bst Solution Code
1