Skip to main content
Talentd

Two Sum BSTs - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersBinary SearchStackTree10 min readAsked at: Amazon
Practice this problem

Problem Statement

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].
  • -109 <= Node.val, target <= 109

Approach Overview

Problem Overview: You are given two binary search trees. The task is to determine whether there exists a node from the first tree and a node from the second tree whose values add up to a given target. Each tree maintains the BST property, which means an in-order traversal produces a sorted sequence of values.

Approach 1: DFS + BST Search (O(n log m) time, O(h) space)

Traverse the first tree using depth-first search. For every visited node with value x, compute target - x and search for that value in the second BST using standard BST lookup. Because BST lookup runs in O(log m) on average, each DFS step performs a fast search in the other tree. The total time becomes O(n log m) for balanced trees, and the recursion stack uses O(h) space where h is the height of the first tree.

This approach directly leverages the BST property and avoids storing all values. It works well when the second tree is balanced and search operations are cheap. In the worst case of a skewed tree, the complexity can degrade to O(nm).

Approach 2: In-order Traversal + Two Pointers (O(n + m) time, O(n + m) space)

Convert both BSTs into sorted arrays using in-order traversal. Since in-order traversal of a BST yields values in ascending order, each traversal produces a sorted list in O(n) and O(m) time. Once both arrays are built, apply the classic two pointers technique.

Start one pointer at the beginning of the first array and another pointer at the end of the second array. If the sum equals the target, a valid pair exists. If the sum is smaller than the target, move the left pointer forward to increase the sum. If the sum is larger, move the right pointer backward to decrease it. Because each pointer moves at most once per element, the scan completes in O(n + m) time.

This method transforms the tree problem into a sorted-array two-sum problem. The tradeoff is extra memory for storing the traversed values, but the algorithm is simple and guarantees linear time.

Recommended for interviews: The in-order traversal + two pointers solution is the expected optimal answer. It demonstrates that you recognize the BST property and can reduce the problem to a sorted two-sum search. Mentioning the DFS + BST lookup approach first shows you understand the tree structure, but the linear-time two-pointer strategy highlights stronger algorithmic thinking.

Solution

We perform in-order traversals on the two trees separately, obtaining two sorted arrays nums[0] and nums[1]. Then we use a two-pointer method to determine whether there exist two numbers whose sum equals the target value. The two-pointer method is as follows:

Initialize two pointers i and j, pointing to the left boundary of array nums[0] and the right boundary of array nums[1] respectively;

Each time, compare the sum x = nums[0][i] + nums[1][j] with the target value. If x = target, return true; otherwise, if x \lt target, move i one step to the right; otherwise, if x \gt target, move j one step to the left.

The time complexity is O(m + n), and the space complexity is O(m + n). Here, m and n are the number of nodes in the two trees respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS + BST SearchO(n log m) averageO(h)When you want to leverage BST lookup without storing extra arrays
In-order Traversal + Two PointersO(n + m)O(n + m)Optimal approach; convert BSTs to sorted arrays and apply two-pointer search

Video Solution

Leetcode 1214. Two Sum BSTs | Logic Coding • Xian Zhang • 394 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Two Sum BSTs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum IV - Input is a BST