Two Sum BSTs

MediumTreestwo pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the roots of two binary search trees, root1 and root2, and an integer target. Return true if there is a node in the first tree and a node in the second tree whose values add up to exactly target, and false otherwise. The two nodes must come from different trees: one from root1 and one from root2. Both trees are non-empty. Checking every pair is O(n * m). Aim for O(n + m).

Examples

Input: root1 = [3,1,6], root2 = [4,2,7], target = 13
Output: true
6 from the first tree plus 7 from the second tree makes 13.
Input: root1 = [3,1,6], root2 = [4,2,7], target = 2
Output: false
The smallest possible sum is 1 + 2 = 3.

Constraints

  • 1 <= number of nodes in each tree <= 5000
  • -10^9 <= Node.val, target <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More two pointers problems