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:
[1, 5000].-109 <= Node.val, target <= 109Problem 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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS + BST Search | O(n log m) average | O(h) | When you want to leverage BST lookup without storing extra arrays |
| In-order Traversal + Two Pointers | O(n + m) | O(n + m) | Optimal approach; convert BSTs to sorted arrays and apply two-pointer search |
Leetcode 1214. Two Sum BSTs | Logic Coding • Xian Zhang • 392 views views
Watch 8 more video solutions →Practice Two Sum BSTs with our built-in code editor and test cases.
Practice on FleetCode