Leetcode 1214. Two Sum BSTs

Problem Explanation

The problem asks us to return True only if there are nodes in two different binary search trees whose sum of values equals to the target integer given. If not, we need to return False.

To explain this problem in simpler terms, let's take an example:

Let's say we have 2 binary search trees as follows,

1
2
3  Tree 1:
4        5
5      /   \
6     3     8
7    / \   / \
8   2   4 7   9
9
10  Tree 2:
11        6
12      /   \
13     4     10
14    / \   /  \
15   3   5 9    11  

And our target sum is 17.

We can see that in Tree 1, there is a node with the value 8 and in Tree 2 there's another node with the value 9. The sum of these two values is 17 which matches our target sum. So in this case, the function should return True.

Now, let's see how to solve this problem using an algorithm.

Approach

The idea of solving this problem is to iterate through each tree, one forwards (from smallest to largest) and the other backwards (from largest to smallest). If the sum of the current two nodes is less than the target, get the next node from the first tree. If the sum of the current two nodes is more than the target, get the next node from the second tree.

Take the above example, we start by calling next() on both iterators, getting 2 from BST1 and 11 from BST2 (2 is the smallest value in BST1 and 11 is the biggest in BST2). The sum is 13 which is less than 17, so we call next() on the iterator of BST1 to get a larger value, which is 3. We continue the process until we find two values whose sum is 17 (8 from BST1 and 9 from BST2) or we've exhausted all possibilities.

Let's demonstrate this approach in code:

Python Solution

1
2python
3class BSTIterator:
4    def __init__(self, root, left_to_right):
5        self.stack = []
6        self.left_to_right = left_to_right
7        self.push_until_null(root)
8        
9    def push_until_null(self, root):
10        while root:
11            self.stack.append(root)
12            root = root.left if self.left_to_right else root.right
13        
14    def next(self):
15        node = self.stack.pop()
16        self.push_until_null(node.right if self.left_to_right else node.left)
17        return node.val
18    
19    def has_next(self):
20        return bool(self.stack)
21        
22class Solution:
23    def twoSumBSTs(self, root1, root2, target):
24        it1, it2 = BSTIterator(root1, True), BSTIterator(root2, False)
25        val1, val2 = it1.next(), it2.next()
26        
27        while True:
28            total = val1 + val2
29            if total == target:
30                return True
31            elif total < target:
32                if not it1.has_next():
33                    return False
34                val1 = it1.next()
35            else:
36                if not it2.has_next():
37                    return False
38                val2 = it2.next()
39        return False

This Python solution uses a class called BSTIterator to handle the iteration through each binary search tree. This class follows the Python iterator protocol, which requires the __init__, next, and has_next methods.

Java Solution

1
2java
3public class Solution {
4    
5    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
6        Stack<TreeNode> stack1 = new Stack(), stack2 = new Stack();
7        while (true) {
8            while (root1 != null) {
9                stack1.push(root1);
10                root1 = root1.left;
11            }
12            while (root2 != null) {
13                stack2.push(root2);
14                root2 = root2.right;
15            }
16            if (stack1.empty() || stack2.empty()) 
17                return false;
18            int total = stack1.peek().val + stack2.peek().val;
19            if (total == target) 
20                return true;
21            else if (total < target) 
22                root1 = stack1.pop().right;
23            else 
24                root2 = stack2.pop().left;
25        }
26    }
27}

In Java solution, we use Stack data structure to keep track of nodes we're currently looking at for both trees. We then have a while loop that continues until it finds a pair of nodes that add up to the target, or until both stacks are empty, indicating that we've exhausted all possibilities.

C++ Solution

1
2c++
3class Solution {
4public:
5    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
6        stack<TreeNode*> s1, s2;
7        while (true) {
8            while (root1 != nullptr) {
9                s1.push(root1);
10                root1 = root1->left;
11            }
12            while (root2 != nullptr) {
13                s2.push(root2);
14                root2 = root2->right;
15            }
16            if (s1.empty() || s2.empty()) 
17                return false;
18            int sum = s1.top()->val + s2.top()->val;
19            if (sum == target) 
20                return true;
21            else if (sum < target) 
22                root1 = s1.top()->right, s1.pop();
23            else 
24                root2 = s2.top()->left, s2.pop();
25        }
26        return false;
27    }
28};

The C++ solution is pretty similar to the Java solution, using a stack to keep track of the nodes we're currently examining in each tree. We keep iterating and manipulating the stacks until we've found a solution or there are no more nodes to examine.## Javascript Solution

1
2javascript
3var twoSumBSTs = function(root1, root2, target) {
4    var stack1 = [], stack2 = [];
5    while (true) {
6        while (root1 != null) {
7            stack1.push(root1);
8            root1 = root1.left;
9        }
10        while (root2 != null) {
11            stack2.push(root2);
12            root2 = root2.right;
13        }
14        if (stack1.length === 0 || stack2.length === 0) {
15            return false;
16        }
17        var sum = stack1[stack1.length - 1].val + stack2[stack2.length - 1].val;
18        if (sum === target) {
19            return true;
20        } else if (sum < target) {
21            root1 = stack1.pop().right;
22        } else {
23            root2 = stack2.pop().left;
24        }
25    }
26};

The solution in Javascript encrypts the BSTs in two Stacks, stack1 and stack2, in in-order and reverse in-order way respectively. So the smallest value and the largest value could be accessed by popping the stacks. If the sum of the smallest and the largest is equal to target, true will be returned. The value less than target means we have to use a larger value from stack1 and vice versa, both by popping and going one step further on that direction in the relevant tree (right in stack1 and left in stack2). And this keeps looping until finding no more elements (all elements exhausted in both trees), which means false should be returned. Hence, the solution is achieved.