⚡Flashcard Drill➔
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

  1. Collect all values of one tree into a hash set.
  2. Then traverse the other tree and check whether target - node.val is in the set.
  3. This is O(m + n) time and O(m) space.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems