Is Two Sum BSTs easy or hard?

Two Sum BSTs is typically classified as a medium-level problem. The challenge comes from recognizing that the BST property allows conversion to sorted arrays and then applying a classic two-pointer search.

How to solve Two Sum BSTs in O(n)?

Perform an in-order traversal on both BSTs to generate two sorted lists of values. Then use a two-pointer approach: one pointer moves forward in the first list and the other moves backward in the second list. Each step adjusts the sum toward the target, producing a linear O(n + m) scan after the traversals.

What is the best approach for Two Sum BSTs?

The most efficient approach uses in-order traversal on both BSTs to produce two sorted arrays, then applies the two pointers technique. One pointer starts at the beginning of the first array and the other at the end of the second array. Adjust pointers based on the sum until a match is found. This runs in O(n + m) time and O(n + m) space.

What data structure is used in Two Sum BSTs?

Binary Search Trees are the primary data structure. The optimal solution also uses arrays generated from in-order traversal and applies the two pointers technique. Alternative approaches rely on depth-first search combined with BST lookup.

What is the time complexity of Two Sum BSTs?

The optimal solution runs in O(n + m) time where n and m are the number of nodes in the two trees. Each tree is traversed once using in-order traversal, and the two-pointer scan processes each element at most once. Space complexity is O(n + m) for storing the traversal results.

Two Sum BSTs Python or Java solution approach?

Python and Java implementations usually perform in-order traversal using recursion or an explicit stack to collect sorted values from both trees. After building the arrays, two pointers compare sums until the target is found. The overall complexity remains O(n + m).

Is Two Sum BSTs asked at Google or Amazon interviews?

Two Sum variations frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests knowledge of binary search trees, traversal techniques, and the two-pointer pattern. Interviewers use it to evaluate how well candidates connect BST properties with array-based algorithms.

Description Hints 3 Solution Video 4:54

1214. Two Sum BSTs

Medium68.2% acceptance1 companyPremium elsewhere, free here

Given the roots of two binary search trees, root1 and root2, 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:

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

Example 2:

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

Constraints:

The number of nodes in each tree is in the range [1, 5000].
-10⁹ <= Node.val, target <= 10⁹

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

How can you reduce this problem to the classical Two Sum problem?

Hint 2

Do an in-order traversal of each tree to convert them to sorted arrays.

Hint 3

Solve the classical Two Sum problem.

4:54

Still stuck?Read the written solution, or watch a walkthrough.

Open solution