NeetCode #407LC-1214MediumTreesNC Algo100
← Back to All Problems#407 · #1214 · Two Sum BSTs(查找两棵二叉搜索树中的两数之和)
📌 Problem Statement & Constraints
Given the roots of two binary search trees and an integer
target, return true if there is a node in the first tree and a node in the second whose values sum to target. Constraints: the number of nodes in each tree is in [1, 5000].💡 Core Algorithmic Approaches
- Collect all values of one tree into a hash set.
- Then traverse the other tree and check whether
target - node.valis in the set. - This is O(m + n) time and O(m) space.
- A more elegant O(m + n) time / O(h1 + h2) space approach uses two iterators over the BSTs in opposite orders (in-order ascending and reverse in-order descending), converging like two pointers.
💻 Benchmark Python3 Implementation
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
seen = set()
def collect(node: Optional[TreeNode]) -> None:
if not node:
return
seen.add(node.val)
collect(node.left)
collect(node.right)
collect(root1)
def check(node: Optional[TreeNode]) -> bool:
if not node:
return False
if target - node.val in seen:
return True
return check(node.left) or check(node.right)
return check(root2)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m + n): one traversal per tree.
💾 Space Complexity
O(m) for the set, where m is the size of the first tree. The two-iterator approach uses only O(h1 + h2).
⚠️ Interview Pitfalls & Follow-ups
- Comparing nodes pairwise: O(m * n) with the naive nested traversal.
- Forgetting that a value may legitimately be 0 or negative: the set handles any integer, so no special case is needed.
- Using a sorted list and binary search: workable, but the hash set is simpler and equally fast.
- Assuming the answer must use the roots: any pair of nodes qualifies.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.