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:
Trueif valid pair exists,Falseotherwise.
Constraints & Edge Cases:
- Tree sizes up to 5000 nodes per tree (). This rules out 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 to . 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 where is height, this results in roughly . While acceptable if trees are balanced (), 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:
- Initialize one pointer at the start of the first list (smallest value).
- Initialize another pointer at the end of the second list (largest value).
- 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, , which is optimal for this problem given we must read every node at least once.
Approach
- 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:
vals1fromroot1andvals2fromroot2. - Two Pointers Initialization: Set pointer
left = 0for the start ofvals1(smallest) andright = len(vals2) - 1for the end ofvals2(largest). - 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
leftto increase the total (since we need a larger value from the first list). - If sum is greater than target, decrement
rightto decrease the total.
- Calculate sum =
- Termination: If pointers cross without finding the pair, return
False.
Complexity Analysis
- Time Complexity: , where and are the number of nodes in each tree. We traverse both trees once () to build lists, then scan them linearly with two pointers (). Total is linear relative to input size.
- Space Complexity: 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 .
- Deep Trees: Iterative in-order traversal is used instead of recursion, preventing
RecursionErroron 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.