LeetCode 1214 - Two Sum BSTs

The problem gives us two binary search trees, root1 and root2, along with an integer target. We must determine whether there exists one node from the first tree and one node from the second tree such that their values add up exactly to target.

leetcodemediumtwo-pointersbinary-searchstacktreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 1214

Difficulty: 🟡 Medium
Topics: Two Pointers, Binary Search, Stack, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us two binary search trees, root1 and root2, along with an integer target. We must determine whether there exists one node from the first tree and one node from the second tree such that their values add up exactly to target.

A binary search tree, or BST, has an important ordering property. For every node, all values in the left subtree are smaller than the node value, and all values in the right subtree are larger. This ordering property allows more efficient searching compared to a regular binary tree.

The input consists of two tree roots and an integer target. Each tree contains between 1 and 5000 nodes, so the total number of nodes across both trees is manageable, but large enough that a quadratic brute-force solution becomes inefficient. Node values and the target may be negative, which means the solution must correctly handle sums involving negative numbers and large integer ranges.

The expected output is a boolean value. We return true if there exists at least one pair of nodes, one from each tree, whose sum equals the target. Otherwise, we return false.

A few important edge cases immediately stand out. One tree may contain very small negative values while the other contains large positive values. The matching pair could involve duplicate values across trees. The valid pair might involve the root nodes directly, or deeply nested nodes. Another important consideration is that the trees are guaranteed to be non-empty, so we never need to handle completely empty input trees. Since values may be as large as 10^9, we must also avoid assumptions about small integer ranges.

Approaches

Brute Force Approach

The most straightforward solution is to compare every node in the first tree with every node in the second tree. We could traverse the first tree and, for each node value x, traverse the second tree searching for a node value equal to target - x.

A truly naive version would perform a complete traversal of the second tree for every node in the first tree. If the first tree contains n nodes and the second tree contains m nodes, this leads to O(n * m) time complexity.

This approach is correct because it checks every possible pair of nodes across the two trees. If any valid pair exists, the brute-force method will eventually find it. However, it is inefficient because it ignores the BST property entirely.

Optimal Approach

The key insight is that BSTs support efficient searching. Instead of scanning the entire second tree for every node in the first tree, we can use BST lookup operations.

We traverse the first tree using DFS. For each node value x, we compute the required complement target - x. We then search the second BST for that complement using standard BST search logic.

Because BST search takes O(h) time, where h is the height of the tree, each lookup becomes much faster than a full traversal. In a balanced BST, this is O(log m) on average.

This approach works because every valid pair must consist of one value from the first tree and one value from the second tree. By checking complements systematically, we guarantee that no valid pair is missed.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(h1 + h2) Compare every node pair
Optimal O(n * h2) average O(h1 + h2) DFS on first tree with BST search in second

Here, h1 and h2 represent the heights of the two trees.

Algorithm Walkthrough

  1. Start a depth-first traversal of the first BST. We visit every node because any node could potentially participate in the target sum.
  2. For each node in the first tree, compute the complement value needed from the second tree. If the current node value is x, the required complement is target - x.
  3. Search for this complement in the second BST using standard BST lookup logic. Because the second tree is a BST, we can efficiently move left or right depending on whether the complement is smaller or larger than the current node.
  4. If the complement exists in the second tree, immediately return true. We have found a valid pair whose sum equals the target.
  5. If the complement is not found, continue DFS traversal into the left and right children of the current node in the first tree.
  6. If the entire first tree is traversed without finding a valid pair, return false.

The algorithm uses recursion because recursive DFS naturally fits tree traversal problems. The BST search operation also becomes very concise and readable with recursion or iterative traversal.

Why it works

The algorithm works because it systematically checks every possible candidate from the first tree. For each candidate value x, it verifies whether the exact complement target - x exists in the second tree. Since BST lookup correctly determines whether a value exists in logarithmic time on average, every valid pair is checked efficiently. If a valid pair exists, the algorithm will eventually encounter the corresponding node in the first tree and successfully locate its complement in the second tree.

Python Solution

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def twoSumBSTs(
        self,
        root1: Optional['TreeNode'],
        root2: Optional['TreeNode'],
        target: int
    ) -> bool:

        def search_bst(node: Optional['TreeNode'], value: int) -> bool:
            while node:
                if node.val == value:
                    return True
                elif value < node.val:
                    node = node.left
                else:
                    node = node.right
            return False

        def dfs(node: Optional['TreeNode']) -> bool:
            if not node:
                return False

            complement = target - node.val

            if search_bst(root2, complement):
                return True

            return dfs(node.left) or dfs(node.right)

        return dfs(root1)

The implementation is divided into two helper functions.

The search_bst function performs standard BST lookup. Starting from the root of the second tree, it repeatedly compares the target value with the current node value. If the target is smaller, it moves left. If larger, it moves right. This leverages the BST ordering property for efficient searching.

The dfs function traverses the first tree using depth-first search. At each node, it calculates the required complement and searches for it in the second tree. If found, it immediately returns True. Otherwise, traversal continues recursively through both subtrees.

The final return statement starts DFS from the root of the first tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {

    var searchBST func(node *TreeNode, value int) bool

    searchBST = func(node *TreeNode, value int) bool {
        for node != nil {
            if node.Val == value {
                return true
            } else if value < node.Val {
                node = node.Left
            } else {
                node = node.Right
            }
        }
        return false
    }

    var dfs func(node *TreeNode) bool

    dfs = func(node *TreeNode) bool {
        if node == nil {
            return false
        }

        complement := target - node.Val

        if searchBST(root2, complement) {
            return true
        }

        return dfs(node.Left) || dfs(node.Right)
    }

    return dfs(root1)
}

The Go implementation closely mirrors the Python version. One notable difference is that Go requires explicit function variable declarations before recursive assignment. We therefore declare searchBST and dfs using var before assigning anonymous functions.

Go uses nil instead of Python's None, and pointer syntax is required for tree node references. Integer overflow is not a concern here because Go's int type comfortably supports the constraint range.

Worked Examples

Example 1

Input:

root1 = [2,1,4]
root2 = [1,0,3]
target = 5

The first BST contains values {1,2,4}.

The second BST contains values {0,1,3}.

We begin DFS on the first tree.

Current Node Complement Needed Search Result in root2
2 3 Found

At the first node itself, the complement 3 exists in the second BST.

Since 2 + 3 = 5, the algorithm immediately returns true.

Example 2

Input:

root1 = [0,-10,10]
root2 = [5,1,7,0,2]
target = 18

First tree values are {-10,0,10}.

Second tree values are {0,1,2,5,7}.

We traverse the first tree.

Current Node Complement Needed Exists in root2
0 18 No
-10 28 No
10 8 No

No complement exists for any node value.

The traversal finishes completely, so the algorithm returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n * h2) average DFS through first tree and BST search in second
Space O(h1 + h2) Recursive call stack and BST traversal

If the second tree is balanced, h2 becomes O(log m), giving average complexity of O(n log m). In the worst case, if the tree is completely skewed, h2 becomes O(m) and the complexity degrades to O(n * m).

The space complexity comes primarily from recursion depth. In balanced trees, recursion depth is logarithmic. In skewed trees, it becomes linear.

Test Cases

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

s = Solution()

# Example 1
root1 = TreeNode(2, TreeNode(1), TreeNode(4))
root2 = TreeNode(1, TreeNode(0), TreeNode(3))
assert s.twoSumBSTs(root1, root2, 5) == True  # basic valid pair

# Example 2
root1 = TreeNode(0, TreeNode(-10), TreeNode(10))
root2 = TreeNode(5, TreeNode(1, TreeNode(0), TreeNode(2)), TreeNode(7))
assert s.twoSumBSTs(root1, root2, 18) == False  # no valid pair

# Single-node trees with valid sum
root1 = TreeNode(1)
root2 = TreeNode(2)
assert s.twoSumBSTs(root1, root2, 3) == True  # smallest valid trees

# Single-node trees without valid sum
root1 = TreeNode(1)
root2 = TreeNode(2)
assert s.twoSumBSTs(root1, root2, 10) == False  # impossible target

# Negative numbers
root1 = TreeNode(-5)
root2 = TreeNode(2)
assert s.twoSumBSTs(root1, root2, -3) == True  # negative + positive

# Deep tree lookup
root1 = TreeNode(8,
    TreeNode(3,
        TreeNode(1),
        TreeNode(6)
    ),
    TreeNode(10)
)

root2 = TreeNode(5,
    TreeNode(2),
    TreeNode(12)
)

assert s.twoSumBSTs(root1, root2, 18) == True  # 6 + 12

# No matching pair in larger trees
root1 = TreeNode(5,
    TreeNode(3),
    TreeNode(8)
)

root2 = TreeNode(1,
    TreeNode(0),
    TreeNode(2)
)

assert s.twoSumBSTs(root1, root2, 20) == False  # no valid pair

# Duplicate values across trees
root1 = TreeNode(4)
root2 = TreeNode(4)
assert s.twoSumBSTs(root1, root2, 8) == True  # same values from different trees
Test Why
Example 1 Verifies standard successful lookup
Example 2 Verifies failure case
Single-node valid Smallest possible success case
Single-node invalid Smallest possible failure case
Negative numbers Ensures negative arithmetic works
Deep tree lookup Tests traversal through deeper BST structure
Larger failure case Confirms full traversal without match
Duplicate values Ensures same value across trees is handled correctly

Edge Cases

One important edge case is when both trees contain only a single node. This is the smallest possible valid input. A careless implementation might assume larger tree structures or incorrectly handle recursion termination. The current implementation handles this naturally because DFS and BST search both correctly process single-node trees.

Another critical edge case involves negative values. Since node values and targets may be negative, the algorithm cannot rely on assumptions about positivity. For example, a valid pair could be -5 + 2 = -3. The implementation uses direct arithmetic comparisons and therefore works correctly regardless of sign.

A third important edge case is highly unbalanced trees. A BST shaped like a linked list causes lookup operations to degrade from logarithmic time to linear time. Recursive depth also becomes much larger. The implementation still produces the correct result because BST traversal logic remains valid even in skewed trees, although performance degrades to worst-case complexity.

A final subtle edge case occurs when the matching pair uses identical values from different trees. For example, 4 in the first tree and 4 in the second tree may sum to 8. The implementation correctly treats nodes from the two trees independently, so identical values are handled without issue.