deepSWE.io

Two Sum IV - Input is a BST

TreesDFSHashing

Problem Statement

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.

Example

Input: root = [5,3,6,2,4,null,7], k = 9

Output: true

Algorithm Explanation

We can solve this problem by traversing the tree and using a hash set to keep track of the values we've seen.

Algorithm Steps

DFS Traversal: We'll use a recursive DFS function to traverse the tree.
Hash Set: We'll use a hash set to store the values of the nodes we have visited.
Check for Complement: At each node, we check if `k - node.val` exists in our hash set. If it does, we've found a pair that sums to `k`, and we can return `true`.
Add to Set: If the complement is not found, we add the current node's value to the hash set and continue the traversal.

Start

Starting DFS from the root.

Found: false

Seen Set

Two Sum IV - Input is a BST Solution


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

        return dfs(root)