02
Intuition
Simplest: it's Two Sum on a tree — DFS with a seen-set. Elegant: inorder gives a sorted array, so converge two pointers from both ends. The BST-iterator version runs both pointers directly on the tree in O(h) space.
03
Approach
1
Hash-set DFS
Visit every node; if k − val is already seen, done. O(n) time and space, any traversal order.
2
Sorted two-pointer alternative
Inorder → sorted list; l from the left, r from the right, steer by sum vs k.
3
Trade-offs
Set version is shortest; two-iterator version wins on space if you already have a BST iterator.
04
Solution & live demo
python
▶1class Solution:
▶2 def findTarget(self, root, k):
▶3 seen = set()
▶4 def dfs(node):
▶5 if not node: return False
▶6 if k - node.val in seen: return True
▶7 seen.add(node.val)
▶8 return dfs(node.left) or dfs(node.right)
▶9 return dfs(root)
05
Edge cases
Same node used twice, k = 2·val
Check the set BEFORE inserting the current value — needs a distinct partner.
Empty or single-node tree
No pair possible → False.
06
Complexity
Time
O(n)
Space
O(n)
Set-based; two-iterator variant is O(h) space.