Recursive
With an inorder traversal, we can sort the values in linear time. Then, we can use two pointers approach to search for the pair, again in linear time.
Time: 
# 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 inorder(self, u, sorted_values) -> None:
if not u:
return
self.inorder(u.left, sorted_values)
sorted_values.append(u.val)
self.inorder(u.right, sorted_values)
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
sorted_values = []
self.inorder(root, sorted_values)
i, j = 0, len(sorted_values)-1
while i < j:
sum = sorted_values[i] + sorted_values[j]
if sum == k:
return True
if sum < k:
i += 1
else:
j -= 1
return False
Keeping track of already seen values, we can search the pair while we are traversing the tree.
# 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 search(self, u, k, seen) -> bool:
if not u:
return False
if (k - u.val) in seen:
return True
seen.add(u.val)
return self.search(u.left, k, seen) or self.search(u.right, k, seen)
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
return self.search(root, k, set())
Iterative
BFS + seen set.
# 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:
if not root:
return False
seen = set()
q = deque([root])
while q:
u = q.popleft()
if (k - u.val) in seen:
return True
seen.add(u.val)
q.extend(c for c in (u.left, u.right) if c)
return False
unreasonably effective 
Leave a comment