LeetCode 1214: Two Sum BSTs Solution

Master LeetCode problem 1214 (Two Sum BSTs), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1214. Two Sum BSTs

Medium

Two Pointers Binary Search Stack Tree Depth-First Search Binary Search Tree Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can use a recursive approach to traverse one of the BSTs while simultaneously checking if the complement of the current node's value exists in the other BST. We can utilize a HashSet to store the values of one of the BSTs and then traverse the other BST to check for the complement.

Algorithm:

Traverse the first BST and store its values in a HashSet.
Traverse the second BST and check if the complement of the current node's value (target - node.val) exists in the HashSet.
If the complement exists, return true. Otherwise, continue traversing both BSTs.
If no pair of nodes are found that sum up to the target, return false.

Time Complexity:

The time complexity of this approach is O(n1 + n2), where n1 and n2 are the number of nodes in the two BSTs.

Space Complexity:

The space complexity is O(n1) to store the values of the first BST in the HashSet.

: :

Solution Code

class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        Set<Integer> set = new HashSet<>();
        traverseAndStore(root1, set);
        return findComplement(root2, set, target);
    }
    
    private void traverseAndStore(TreeNode node, Set<Integer> set) {
        if (node == null) return;
        set.add(node.val);
        traverseAndStore(node.left, set);
        traverseAndStore(node.right, set);
    }
    
    private boolean findComplement(TreeNode node, Set<Integer> set, int target) {
        if (node == null) return false;
        if (set.contains(target - node.val)) return true;
        return findComplement(node.left, set, target) || findComplement(node.right, set, target);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1214 (Two Sum BSTs)?

This page provides optimized solutions for LeetCode problem 1214 (Two Sum BSTs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1214 (Two Sum BSTs)?

The time complexity for LeetCode 1214 (Two Sum BSTs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1214 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1214 in Java, C++, or Python.

Back to LeetCode Solutions