Reference: LeetCode
Difficulty: Medium

Problem

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example:

1
2
3
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.

1
2
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Note:

  • Each tree has at most 5000 nodes.
  • -10^9 <= target, node.val <= 10^9

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
if (root1 == null) {
return false;
}
// visit
if (find(root2, target - root1.val)) {
return true;
}
return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1.right, root2, target);
}

private boolean find(TreeNode root, int target) {
if (root == null) {
return false;
}
if (target == root.val) {
return true;
} else if (target < root.val) {
return find(root.left, target);
} else {
return find(root.right, target);
}
}

Time: $O(MN)$
Space: $O(\max{(M, N)})$

Two Pointers

Convert to two lists list1 and list2, then apply the two-pointer method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
// Convert to list
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
listByInorder(root1, list1);
listByInorder(root2, list2);
// Two Pointers
int lo = 0, hi = list2.size() - 1;
while (lo < list1.size() && hi >= 0) { // notice the condition here
int sum = list1.get(lo) + list2.get(hi);
if (sum == target) {
return true;
} else if (sum < target) {
++lo;
} else {
--hi;
}
}
return false;
}

private void listByInorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
listByInorder(root.left, list);
list.add(root.val);
listByInorder(root.right, list);
}

Time: $O(M + N)$
Space: $O(\log{\max{(M, N)}})$ in the best case; $O(\max{(M, N)})$ in the worst case.