Two Sum BSTs

medium binary search tree inorder two pointers

Problem

Given the roots of two binary search trees, root1 and root2, and an integer target, return true if and only if there is a node in the first tree and a node in the second tree whose values sum to target.

Inputroot1 = [2, 1, 4], root2 = [1, 0, 3], target = 5

Outputtrue

Inorder of root1 is [1, 2, 4] and of root2 is [0, 1, 3]. The pair 2 (from tree 1) and 3 (from tree 2) sums to 5.

tree 1 inorder (sorted, comma-separated)

tree 2 inorder (sorted, comma-separated)

target

def two_sum_bsts(root1, root2, target):
    def inorder(node, out):
        if not node:
            return
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    a, b = [], []
    inorder(root1, a)
    inorder(root2, b)
    i, j = 0, len(b) - 1
    while i < len(a) and j >= 0:
        s = a[i] + b[j]
        if s == target:
            return True
        if s < target:
            i += 1
        else:
            j -= 1
    return False

function twoSumBSTs(root1, root2, target) {
  const inorder = (node, out) => {
    if (!node) return;
    inorder(node.left, out);
    out.push(node.val);
    inorder(node.right, out);
  };
  const a = [], b = [];
  inorder(root1, a);
  inorder(root2, b);
  let i = 0, j = b.length - 1;
  while (i < a.length && j >= 0) {
    const s = a[i] + b[j];
    if (s === target) return true;
    if (s < target) i++;
    else j--;
  }
  return false;
}

class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
        inorder(root1, a);
        inorder(root2, b);
        int i = 0, j = b.size() - 1;
        while (i < a.size() && j >= 0) {
            int s = a.get(i) + b.get(j);
            if (s == target) return true;
            if (s < target) i++;
            else j--;
        }
        return false;
    }
    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }
}

class Solution {
public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        vector<int> a, b;
        inorder(root1, a);
        inorder(root2, b);
        int i = 0, j = (int)b.size() - 1;
        while (i < (int)a.size() && j >= 0) {
            int s = a[i] + b[j];
            if (s == target) return true;
            if (s < target) i++;
            else j--;
        }
        return false;
    }
    void inorder(TreeNode* node, vector<int>& out) {
        if (!node) return;
        inorder(node->left, out);
        out.push_back(node->val);
        inorder(node->right, out);
    }
};

Explanation

We need one value from the first BST and one from the second that together hit target. The key idea is that an in-order traversal of a BST produces a sorted list, and two sorted lists are perfect for a fast two-pointer scan.

First the helper inorder flattens each tree into sorted arrays a and b. Then we place pointer i at the start of a (smallest) and pointer j at the end of b (largest).

At each step we look at the sum s = a[i] + b[j]. If it equals target we are done. If it is too small, we move i right to grow the sum; if it is too big, we move j left to shrink it. This squeezes toward the answer without rechecking pairs.

Example: a = [1,2,4], b = [0,1,3], target = 5. Starting at 1 + 3 = 4 (too small) we move i; 2 + 3 = 5 matches, so the answer is true.

Building the lists is O(n + m) and the scan is linear, so overall it is O(n + m).

Time: O(m + n) Space: O(m + n)