Two Sum BSTs - Video Solutions
Leetcode 1214. Two Sum BSTs | Logic Coding
Two Sum BSTs - Video Solution
Watch 10 video solutions for Two Sum BSTs, a medium level problem involving Two Pointers, Binary Search, Stack. This walkthrough by Xian Zhang has 394 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Complexity Analysis
| 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 |