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.