_653. Two Sum IV - Input is a BST.md

653. Two Sum IV - Input is a BST

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 31, 2024

Last updated : July 31, 2024

---

Related Topics : Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Acceptance Rate : 61.63 %

---

Solutions

• e653.py

Python

e653.py

# 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:
        counterpartVals = set()

        def dfs(curr: Optional[TreeNode]) -> bool :
            if not curr :
                return False
            if curr.val in counterpartVals :
                return True
            counterpartVals.add(k - curr.val)
            return dfs(curr.left) or dfs(curr.right)
        
        return dfs(root)