Prerequisites
Before attempting this problem, you should be comfortable with:
- Binary Search Tree (BST) properties - Understanding that inorder traversal yields sorted values and how to search in O(log n) time
- Tree traversal (DFS) - Recursively visiting all nodes to collect values or search for complements
- Hash Sets - Storing values for O(1) lookup when checking if a complement exists
- Two Pointers technique - Using pointers on sorted lists to efficiently find pairs that sum to a target
1. Brute Force
Intuition
The simplest approach is to collect all values from both trees and check every possible pair. If any pair sums to the target, we have found our answer.
Algorithm
- Traverse the first tree and store all node values in a list.
- Traverse the second tree and store all node values in another list.
- For each value
ain the first list and each valuebin the second list, check ifa + b == target. - Return
trueif a valid pair is found,falseotherwise.
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def dfs(curr_node, node_list):
if not curr_node:
return
node_list.append(curr_node.val)
dfs(curr_node.left, node_list)
dfs(curr_node.right, node_list)
node_list1, node_list2 = [], []
dfs(root1, node_list1)
dfs(root2, node_list2)
for a in node_list1:
for b in node_list2:
if a + b == target:
return True
return FalseTime & Space Complexity
- Time complexity:
- Space complexity:
Where and are the number of nodes in the two trees.
2. Binary Search
Intuition
Since the second tree is a BST, we can leverage its sorted structure. For each node in the first tree, we compute the complement (target - node.val) and use binary search to check if that complement exists in the second tree.
Algorithm
- Traverse the first BST using
dfs. - For each node with value
v, computecomplement = target - v. - Perform binary search in the second BST to find the complement:
- If current value equals
complement, returntrue. - If current value is greater, search left.
- Otherwise, search right.
- If current value equals
- If no pair is found after checking all nodes, return
false.
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def binarySearch(root2, target2):
if not root2:
return False
if root2.val == target2:
return True
elif root2.val > target2:
return binarySearch(root2.left, target2)
else:
return binarySearch(root2.right, target2)
def dfs(root, target):
if not root:
return False
if binarySearch(root2, target - root.val):
return True
return dfs(root.left, target) or dfs(root.right, target)
return dfs(root1, target)Time & Space Complexity
- Time complexity:
- Space complexity:
Where and are the number of nodes in the two trees.
3. Hash Set
Intuition
We can trade space for time by storing all values from one tree in a hash set. Then for each value in the other tree, we check if the complement exists in the set in O(1) time.
Algorithm
- Traverse the first tree and add all values to a hash set.
- Traverse the second tree and add all values to another hash set.
- For each value in the first set, check if
target - valueexists in the second set. - Return
trueif found,falseotherwise.
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def dfs(curr_node, node_set):
if not curr_node:
return
dfs(curr_node.left, node_set)
node_set.add(curr_node.val)
dfs(curr_node.right, node_set)
node_set1, node_set2 = set(), set()
dfs(root1, node_set1)
dfs(root2, node_set2)
for value1 in node_set1:
if target - value1 in node_set2:
return True
return FalseTime & Space Complexity
- Time complexity:
- Space complexity:
Where and are the number of nodes in the two trees.
4. Two Pointers
Intuition
An inorder traversal of a BST produces a sorted list. If we have sorted lists from both trees, we can use the classic two-pointer technique: one pointer starts at the beginning of the first list (smallest), and another starts at the end of the second list (largest). We adjust pointers based on whether the current sum is too small or too large.
Algorithm
- Perform inorder traversal on both trees to get two sorted lists.
- Initialize
pointer1 = 0(start of first list) andpointer2 = len(list2) - 1(end of second list). - While both pointers are valid:
- If sum equals
target, returntrue. - If sum is less than
target, incrementpointer1. - If sum is greater than
target, decrementpointer2.
- If sum equals
- Return
falseif no pair is found.
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def dfs(curr_node, node_list):
if not curr_node:
return
dfs(curr_node.left, node_list)
node_list.append(curr_node.val)
dfs(curr_node.right, node_list)
node_list1, node_list2 = [], []
dfs(root1, node_list1)
dfs(root2, node_list2)
pointer1 = 0
pointer2 = len(node_list2) - 1
while pointer1 < len(node_list1) and pointer2 >= 0:
if node_list1[pointer1] + node_list2[pointer2] == target:
return True
elif node_list1[pointer1] + node_list2[pointer2] < target:
pointer1 += 1
else:
pointer2 -= 1
return FalseTime & Space Complexity
- Time complexity:
- Space complexity:
Where and are the number of nodes in the two trees.
5. Morris Traversal
Intuition
The two-pointer approach requires O(m + n) space to store the sorted lists. Morris traversal lets us iterate through a BST in sorted order using O(1) extra space by temporarily modifying tree pointers. We use forward Morris traversal on one tree and reverse Morris traversal on the other to simulate the two-pointer technique without extra space.
Algorithm
- Create a forward Morris iterator for the first tree (yields values in ascending order).
- Create a reverse Morris iterator for the second tree (yields values in descending order).
- Get the first value from each iterator.
- While both values are valid:
- If sum equals
target, returntrue. - If sum is less than
target, advance the forward iterator. - If sum is greater than
target, advance the reverse iterator.
- If sum equals
- Return
falseif no pair is found.
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def morris_traversal(root):
current = root
while current:
if not current.left:
yield current.val
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
yield current.val
current = current.right
def reversed_morris_traversal(root):
current = root
while current:
if not current.right:
yield current.val
current = current.left
else:
pre = current.right
while pre.left and pre.left != current:
pre = pre.left
if not pre.left:
pre.left = current
current = current.right
else:
pre.left = None
yield current.val
current = current.left
iterater1 = morris_traversal(root1)
iterater2 = reversed_morris_traversal(root2)
value1 = next(iterater1, None)
value2 = next(iterater2, None)
while value1 is not None and value2 is not None:
if value1 + value2 == target:
return True
elif value1 + value2 < target:
value1 = next(iterater1, None)
else:
value2 = next(iterater2, None)
return FalseTime & Space Complexity
- Time complexity:
- Space complexity:
Where and are the number of nodes in the two trees.
Common Pitfalls
Treating the Trees as Regular Binary Trees
A common mistake is ignoring the BST property and treating both trees as generic binary trees. This leads to inefficient solutions that don't leverage the sorted structure for binary search or two-pointer approaches. Always consider whether the BST ordering can help optimize your search.
Computing the Complement Incorrectly
When searching for a pair that sums to the target, some forget to compute target - value correctly or accidentally search for the wrong value. For example, if target = 9 and the current node has value 4, you need to search for 5 in the other tree, not 9 - 4 = 5 with any other formula.
Modifying Tree Structure with Morris Traversal
Morris traversal temporarily modifies tree pointers to achieve O(1) space. A pitfall is forgetting to restore the original tree structure after traversal or exiting early without cleanup. This can corrupt the tree for subsequent operations or cause infinite loops.