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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.