Two Sum IV - Input is a BST

Difficulty: Easy | Acceptance: 63.30% | Paid: No Topics: Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

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

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Set
• Approach 3: Two Pointers

Examples

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Explanation: 5 + 4 = 9.

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

Approach 1: Brute Force

Intuition The simplest approach is to traverse the tree to collect all node values into a list, then use nested loops to check every possible pair to see if their sum equals k.

Steps

• Perform a traversal (DFS or BFS) to extract all node values into a list.
• Use two nested loops to iterate through all pairs of values.
• If a pair sums to k, return true. If the loop finishes without finding a pair, return false.

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        vals = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        n = len(vals)
        for i in range(n):
            for j in range(i + 1, n):
                if vals[i] + vals[j] == k:
                    return True
        return False

Complexity

• Time: O(n²) where n is the number of nodes.
• Space: O(n) to store the values.
• Notes: Simple but inefficient for large trees.

Approach 2: Hash Set

Intuition We can traverse the tree while maintaining a set of seen values. For each node, we check if the complement (k - node.val) exists in the set. If it does, we found a pair.

Steps

• Initialize an empty hash set.
• Traverse the tree using DFS or BFS.
• For each node, calculate complement = k - node.val.
• If complement is in the set, return true.
• Otherwise, add node.val to the set and continue.
• If traversal finishes, return false.

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()
        stack = [root]
        
        while stack:
            node = stack.pop()
            complement = k - node.val
            if complement in seen:
                return True
            seen.add(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return False

Complexity

• Time: O(n) where n is the number of nodes.
• Space: O(n) for the hash set.
• Notes: Efficient and easy to implement.

Approach 3: Two Pointers

Intuition Since the input is a BST, an inorder traversal yields a sorted list of values. We can then use the two-pointer technique on this sorted list to find if two numbers sum to k.

Steps

• Perform an inorder traversal to get a sorted list of values.
• Initialize two pointers, left at the start and right at the end of the list.
• While left < right:
  • Calculate sum = vals[left] + vals[right].
  • If sum == k, return true.
  • If sum < k, increment left to increase the sum.
  • If sum > k, decrement right to decrease the sum.
• Return false if the loop ends.

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        vals = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        left, right = 0, len(vals) - 1
        
        while left < right:
            current_sum = vals[left] + vals[right]
            if current_sum == k:
                return True
            elif current_sum < k:
                left += 1
            else:
                right -= 1
        return False

Complexity

• Time: O(n) where n is the number of nodes.
• Space: O(n) to store the sorted list.
• Notes: Leverages the BST property for an efficient search without a hash set.