Problem Description

You are given two binary search trees with roots root1 and root2, along with an integer target. Your task is to determine if there exists a node in the first tree and a node in the second tree such that the sum of their values equals target.

The problem asks you to return true if such a pair of nodes exists (one from each tree), and false otherwise.

For example, if the first BST contains nodes with values [2, 3, 5] and the second BST contains nodes with values [1, 4, 6], and target = 7, then you would return true because there exists a node with value 3 in the first tree and a node with value 4 in the second tree, and 3 + 4 = 7.

The solution leverages the property of BSTs that an in-order traversal produces a sorted sequence. By performing in-order traversal on both trees, we get two sorted arrays. Then, using a two-pointer technique with one pointer starting from the beginning of the first array and another from the end of the second array, we can efficiently find if any pair sums to the target value. This works because:

• If the current sum is less than target, we need a larger sum, so we move the left pointer forward (to get a larger value from the first array)
• If the current sum is greater than target, we need a smaller sum, so we move the right pointer backward (to get a smaller value from the second array)
• If the sum equals target, we've found our pair and return true

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While the problem involves binary search trees, trees are a special type of graph (acyclic connected graphs). We have two tree structures that we need to traverse.

Is it a tree?

• Yes: The problem explicitly states we're working with two binary search trees (root1 and root2). We need to examine nodes from both trees.

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice. This is the natural traversal method for trees when we need to visit all nodes to collect their values.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for traversing both binary search trees.

The solution implements DFS through the recursive dfs function that performs an in-order traversal on each tree. This traversal pattern visits the left subtree first, then the current node, then the right subtree, which is characteristic of depth-first search. The in-order DFS traversal is particularly useful here because it gives us the values in sorted order for BSTs, which enables the efficient two-pointer technique to find if any pair of values sums to the target.

Intuition

The key insight comes from recognizing that we need to find two numbers (one from each tree) that sum to a target value. This is essentially a variant of the classic two-sum problem, but instead of finding two numbers in a single array, we're finding them across two different trees.

Since we're dealing with Binary Search Trees (BSTs), we can leverage their special property: an in-order traversal always gives us values in sorted order. This is crucial because having sorted sequences opens up efficient search strategies.

Why not just check every possible pair? While we could traverse the first tree and for each value check if target - value exists in the second tree, this would be inefficient, requiring multiple tree searches.

Instead, we can transform the problem:

1. Extract all values from both trees into sorted arrays using in-order DFS traversal
2. Now we have two sorted arrays and need to find one element from each that sum to target

With two sorted arrays, the two-pointer technique becomes natural. We place one pointer at the start of the first array (smallest value) and another at the end of the second array (largest value). This setup gives us:

• If nums[0][i] + nums[1][j] < target, we need a larger sum, so we move the left pointer right to get a bigger value from the first array
• If nums[0][i] + nums[1][j] > target, we need a smaller sum, so we move the right pointer left to get a smaller value from the second array
• If the sum equals target, we've found our answer

This approach is elegant because it combines the BST property (sorted in-order traversal) with the two-pointer technique to solve the problem in linear time after the traversals, avoiding the need for nested loops or repeated tree searches.

Learn more about Stack, Tree, Depth-First Search, Binary Search Tree, Two Pointers, Binary Search and Binary Tree patterns.

Solution Approach

The solution implements the strategy outlined in the reference approach: In-order Traversal + Two Pointers.

Step 1: In-order Traversal using DFS

The solution defines a recursive dfs function that performs in-order traversal:

def dfs(root: Optional[TreeNode], i: int):
    if root is None:
        return
    dfs(root.left, i)      # Visit left subtree
    nums[i].append(root.val)  # Process current node
    dfs(root.right, i)     # Visit right subtree

The function takes two parameters:

• root: The current node being visited
• i: An index (0 or 1) indicating which tree we're traversing

The in-order traversal ensures that values are added to nums[i] in sorted order because of the BST property (left < root < right).

Step 2: Initialize Data Structures

nums = [[], []]  # Two empty lists to store values from each [tree](/problems/tree_intro)
dfs(root1, 0)    # Populate nums[0] with values from first tree
dfs(root2, 1)    # Populate nums[1] with values from second tree

After these calls, nums[0] contains all values from the first BST in ascending order, and nums[1] contains all values from the second BST in ascending order.

Step 3: Two-Pointer Search

i, j = 0, len(nums[1]) - 1  # i starts at beginning of first array, j at end of second
while i < len(nums[0]) and ~j:  # Continue while both pointers are valid
    x = nums[0][i] + nums[1][j]
    if x == target:
        return True
    if x < target:
        i += 1  # Need larger sum, move left pointer right
    else:
        j -= 1  # Need smaller sum, move right pointer left

The two-pointer logic works because:

• When the sum is too small, incrementing i gives us a larger value from the first array
• When the sum is too large, decrementing j gives us a smaller value from the second array
• The condition ~j is a bitwise check equivalent to j >= 0, ensuring j hasn't gone below 0

Time Complexity: O(m + n) where m and n are the number of nodes in the two trees respectively. We traverse each tree once and then perform a linear scan with two pointers.

Space Complexity: O(m + n) for storing the values from both trees in the nums arrays.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Tree 1 (BST):

    5
   / \
  3   7
 /
2

• Tree 2 (BST):

    4
   / \
  1   6

• Target: 9

Step 1: In-order Traversal

First, we perform in-order traversal on both trees to extract their values in sorted order.

For Tree 1:

• Visit left subtree of 5 → Visit left subtree of 3 → Visit 2 (leaf)
• Add 2 to nums[0]: [2]
• Back to 3, add 3: [2, 3]
• No right child of 3, back to 5, add 5: [2, 3, 5]
• Visit right subtree of 5 → Visit 7 (leaf)
• Add 7 to nums[0]: [2, 3, 5, 7]

For Tree 2:

• Visit left subtree of 4 → Visit 1 (leaf)
• Add 1 to nums[1]: [1]
• Back to 4, add 4: [1, 4]
• Visit right subtree of 4 → Visit 6 (leaf)
• Add 6 to nums[1]: [1, 4, 6]

Result: nums = [[2, 3, 5, 7], [1, 4, 6]]

Step 2: Two-Pointer Search

Initialize pointers:

• i = 0 (pointing to nums[0][0] = 2)
• j = 2 (pointing to nums[1][2] = 6)

Iteration 1:

• Sum = nums[0][0] + nums[1][2] = 2 + 6 = 8
• 8 < 9 (target), so we need a larger sum
• Move i forward: i = 1

Iteration 2:

• Sum = nums[0][1] + nums[1][2] = 3 + 6 = 9
• 9 == 9 (target)
• Found! Return true

The algorithm successfully finds that node with value 3 from Tree 1 and node with value 6 from Tree 2 sum to our target of 9.

Why Two Pointers Works Here:

The key insight is that by starting with the smallest value from the first array and the largest from the second array, we can systematically explore all possibilities:

• If our sum is too small, we can only increase it by moving the left pointer right (getting a larger value from the first array)
• If our sum is too large, we can only decrease it by moving the right pointer left (getting a smaller value from the second array)
• This guarantees we'll find the target sum if it exists, without checking every possible pair

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n)

The algorithm consists of two main phases:

1. Tree Traversal Phase: The dfs function performs an in-order traversal on both BSTs. For root1 with m nodes, the traversal takes O(m) time. For root2 with n nodes, the traversal takes O(n) time.
2. Two-Pointer Search Phase: The while loop uses two pointers to search for the target sum. In the worst case, pointer i traverses all m elements of nums[0] or pointer j traverses all n elements of nums[1]. This takes at most O(m + n) time.

Total time complexity: O(m) + O(n) + O(m + n) = O(m + n)

Space Complexity: O(m + n)

The space usage includes:

1. Explicit Storage: The nums list stores all values from both trees. nums[0] stores m values from root1, and nums[1] stores n values from root2, requiring O(m + n) space.
2. Recursion Stack: The dfs function uses recursion for tree traversal. In the worst case (skewed tree), the recursion depth equals the tree height. For a BST with m nodes, this is O(m) in the worst case, and similarly O(n) for the second tree. However, since the traversals are done sequentially (not simultaneously), the maximum stack space used at any point is O(max(m, n)).

Since O(m + n) dominates O(max(m, n)), the total space complexity is O(m + n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting In-place Traversal with Generators/Iterators

A common pitfall is trying to optimize space by using iterators or generators for the in-order traversal instead of storing all values, thinking this would save memory:

# Problematic approach - trying to use generators
def inorder_generator(root):
    if root:
        yield from inorder_generator(root.left)
        yield root.val
        yield from inorder_generator(root.right)

# Then trying to use two pointers on generators
gen1 = inorder_generator(root1)
gen2 = inorder_generator(root2)
# This doesn't work because you can't move backwards in a generator!

Why this fails: The two-pointer technique requires the ability to move backwards in the second array (decrementing the right pointer). Generators only allow forward iteration, making it impossible to implement the two-pointer approach correctly.

Solution: Stick with storing the values in arrays as shown in the original solution. While this uses O(m+n) space, it's necessary for the two-pointer technique to work efficiently.

2. Incorrect Boundary Check for the Right Pointer

Another pitfall is using incorrect conditions for checking the right pointer bounds:

# Incorrect - using wrong operator
while i < len(nums[0]) and j > 0:  # Bug: misses j=0 case
    # ... rest of code

# Also incorrect - checking after access
while i < len(nums[0]):
    x = nums[0][i] + nums[1][j]  # Can cause IndexError when j < 0
    if j < 0:
        break

Why this fails: The first version stops prematurely when j=0, missing valid combinations with the first element of the second array. The second version may cause an IndexError by accessing nums[1][j] when j becomes negative.

Solution: Always check j >= 0 (or use ~j for the bitwise equivalent) in the while condition before accessing the array:

while i < len(nums[0]) and j >= 0:
    x = nums[0][i] + nums[1][j]
    # ... rest of code

3. Forgetting BST Properties During Manual Testing

When testing or debugging, developers sometimes create test cases with non-BST structures:

# Invalid test case - not a valid BST
#       5
#      / \
#     7   3  # Left child (7) is greater than parent (5)!

Why this fails: The algorithm relies on the BST property to ensure in-order traversal produces sorted arrays. With invalid BST input, the two-pointer technique won't work correctly.

Solution: Always validate that test inputs are valid BSTs. When constructing test cases, ensure:

• All values in the left subtree < node value
• All values in the right subtree > node value
• This property holds recursively for all subtrees