Domain 2MediumMEDIUM

Two Sum BSTs

Determines if two BSTs contain a pair of nodes that sum to target using in-order traversal and the two-pointer technique.

Domain: medium•Updated: 2026-09-10
#Two Pointers#In-Order Traversal#O(N + M)#BST

Problem Breakdown

We are given roots of two Binary Search Trees (root1, root2) and an integer target. We need to return a boolean indicating if there exist nodes in both trees such that their values sum exactly to target.

Inputs:

  • Two BST root nodes.
  • An integer target value.

Outputs:

  • Boolean: True if valid pair exists, False otherwise.

Constraints & Edge Cases:

  • Tree sizes up to 5000 nodes per tree (N≤5000N \le 5000). This rules out O(N2)O(N^2) solutions like nested loops or searching the second tree for every node in the first without optimization (though optimized search is better, two-pointers on sorted lists is optimal linear time).
  • Values range from −109-10^9 to 10910^9. Python handles large integers natively.
  • BST property: Left child < Parent < Right child. This guarantees that an in-order traversal yields a strictly increasing sequence of values (assuming distinct keys, or non-decreasing if duplicates allowed).

Intuition

A naive solution would iterate through every node in root1 and perform a search for the complement (target - val) in root2. Since BST search is O(H)O(H) where HH is height, this results in roughly O(N⋅H)O(N \cdot H). While acceptable if trees are balanced (Nlog⁡NN \log N), it doesn’t fully exploit the sorted nature of both datasets.

Key Insight: Binary Search Trees produce values in sorted order when traversed via In-Order Traversal (Left -> Root -> Right). If we extract all node values from both trees into two separate lists (vals1, vals2), they become naturally sorted arrays.

The problem then reduces to the classic “Two Sum” on Sorted Arrays, which can be solved efficiently using the two-pointer technique:

  1. Initialize one pointer at the start of the first list (smallest value).
  2. Initialize another pointer at the end of the second list (largest value).
  3. Check sums and move pointers inward based on whether the current sum is less than or greater than target.

This approach runs in linear time relative to the number of nodes, O(N+M)O(N + M), which is optimal for this problem given we must read every node at least once.

Approach

  1. Extract Sorted Data: Perform an iterative In-Order Traversal on both trees using a stack-based DFS. This avoids recursion depth limits and produces two sorted lists of integers: vals1 from root1 and vals2 from root2.
  2. Two Pointers Initialization: Set pointer left = 0 for the start of vals1 (smallest) and right = len(vals2) - 1 for the end of vals2 (largest).
  3. Search Loop: While both pointers are within valid bounds:
    • Calculate sum = vals1[left] + vals2[right].
    • If sum equals target, return True.
    • If sum is less than target, increment left to increase the total (since we need a larger value from the first list).
    • If sum is greater than target, decrement right to decrease the total.
  4. Termination: If pointers cross without finding the pair, return False.

Complexity Analysis

  • Time Complexity: O(N+M)O(N + M), where NN and MM are the number of nodes in each tree. We traverse both trees once (O(N+M)O(N+M)) to build lists, then scan them linearly with two pointers (O(N+M)O(N+M)). Total is linear relative to input size.
  • Space Complexity: O(N+M)O(N + M) to store the values from both trees during traversal (excluding recursion stack space if iterative DFS is used). For 5000 nodes per tree, this fits well within standard memory limits (~80KB for integers).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root) -> list[int]:
    """Iterative in-order traversal to get sorted values from a BST."""
    res = []
    stack = []
    curr = root
    
    while curr or stack:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            node = stack.pop()
            res.append(node.val)
            curr = node.right
            
    return res

def twoSumBSTs(root1, root2, target):
    # Extract sorted values from both BSTs using in-order traversal.
    # This transforms the tree problem into a Two Sum on Sorted Arrays problem.
    vals1 = inorder(root1)
    vals2 = inorder(root2)
    
    left, right = 0, len(vals2) - 1
    
    while left < len(vals1) and right >= 0:
        current_sum = vals1[left] + vals2[right]
        
        if current_sum == target:
            return True
        
        elif current_sum < target:
            # Sum is too small, need larger value from the first tree (sorted ascending).
            left += 1
        else:
            # Sum is too large, need smaller value from the second tree.
            right -= 1
            
    return False

Edge Cases Handled

  • Large Values: Python handles integers of arbitrary size; no overflow issues for inputs up to 10910^9.
  • Deep Trees: Iterative in-order traversal is used instead of recursion, preventing RecursionError on trees with depth > 1000.
  • No Match Found: The loop terminates correctly when pointers cross without finding the target sum, returning False.
  • Single Node Trees: Logic holds for lists of length 1; two-pointer logic adjusts immediately to check or terminate appropriately.