Problem Statement
Given two binary search trees each represented by their roots named root1 and root2, the goal is to determine if there exist at least two nodes, one from each tree, whose values add up to a specific target number. This check must return true if such a pair exists and false otherwise. This problem tests the understanding of tree traversal, hashing, and handling of binary search trees.
Examples
Example 1
Input:
root1 = [2,1,4], root2 = [1,0,3], target = 5
Output:
true
Explanation:
2 and 3 sum up to 5.
Example 2
Input:
root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output:
false
Constraints
- The number of nodes in each tree is in the range
[1, 5000]. -109 <= Node.val, target <= 109
Approach and Intuition
The task involves finding two numbers from two different binary search trees (BSTs) that sum up to a given target. Here's a conceptual breakdown of how one can approach this:
We can utilize the properties of a BST where for any given node, left children have smaller values and right children have greater values. This ordering can facilitate searching.
One efficient approach is using a two-pointer technique but applied in the tree context, which implies an iterative or recursive in-order traversal for BSTs. Given that the in-order traversal of a BST yields elements in a sorted order, we can virtually think of it as applying two pointers on two sorted arrays.
Another approach involves the usage of hashing:
- Traverse the first tree and store its node values in a hash set.
- While traversing the second tree, for each node check if
target - node.valis already in the hash set. If it is, that means a pair has been found that sums up to the target.
Key Points from Examples
Example 1:
- Trees:
root1= [2,1,4],root2= [1,0,3] and target = 5. - A simple inspection using the hash set approach reveals 2 in
root1and 3 inroot2sum up to 5. The result istrue.
- Trees:
Example 2:
- Trees:
root1= [0,-10,10],root2= [5,1,7,0,2] and target = 18. - Checking all combinations shows no pair adds up to 18. Here, confirmatory searching didn't find a valid pair, hence the answer is
false.
- Trees:
Constraints Implications
- Up to 5000 nodes in each tree hint at the efficiency requirement; approaches that could lead to a worse case scenario of quadratic runtime (O(n*m)) might not be suitable.
- The large range of node values shows that memory and handling of integers in computations need to be managed carefully.
Solutions
- Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int value;
* TreeNode leftNode;
* TreeNode rightNode;
* TreeNode() {}
* TreeNode(int value) { this.value = value; }
* TreeNode(int value, TreeNode leftNode, TreeNode rightNode) {
* this.value = value;
* this.leftNode = leftNode;
* this.rightNode = rightNode;
* }
* }
*/
class InorderMorrisTraversal implements Iterator<Integer> {
private TreeNode node;
private TreeNode predecessor;
public InorderMorrisTraversal(TreeNode root) {
node = root;
predecessor = null;
}
public boolean hasNext() {
return node != null;
}
public Integer next() {
Integer val = null;
while (node != null) {
if (node.leftNode == null) {
val = node.value;
node = node.rightNode;
break;
} else {
predecessor = node.leftNode;
while (predecessor.rightNode != null && predecessor.rightNode != node) {
predecessor = predecessor.rightNode;
}
if (predecessor.rightNode == null) {
predecessor.rightNode = node;
node = node.leftNode;
} else {
predecessor.rightNode = null;
val = node.value;
node = node.rightNode;
break;
}
}
}
return val;
}
}
class ReverseInorderMorrisTraversal implements Iterator<Integer> {
private TreeNode node;
private TreeNode predecessor;
public ReverseInorderMorrisTraversal(TreeNode root) {
node = root;
predecessor = null;
}
public boolean hasNext() {
return node != null;
}
public Integer next() {
Integer val = null;
while (node != null) {
if (node.rightNode == null) {
val = node.value;
node = node.leftNode;
break;
} else {
predecessor = node.rightNode;
while (predecessor.leftNode != null && predecessor.leftNode != node) {
predecessor = predecessor.leftNode;
}
if (predecessor.leftNode == null) {
predecessor.leftNode = node;
node = node.rightNode;
} else {
predecessor.leftNode = null;
val = node.value;
node = node.leftNode;
break;
}
}
}
return val;
}
}
class Solution {
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
InorderMorrisTraversal iterator1 = new InorderMorrisTraversal(root1);
ReverseInorderMorrisTraversal iterator2 = new ReverseInorderMorrisTraversal(root2);
int value1 = iterator1.next(), value2 = iterator2.next();
while (value1 != Integer.MIN_VALUE && value2 != Integer.MIN_VALUE) {
if (value1 + value2 == target) {
return true;
} else if (value1 + value2 < target) {
if (iterator1.hasNext()) {
value1 = iterator1.next();
} else {
value1 = Integer.MIN_VALUE;
}
} else {
if (iterator2.hasNext()) {
value2 = iterator2.next();
} else {
value2 = Integer.MIN_VALUE;
}
}
}
return false;
}
}
The provided Java solution tackles the problem of determining whether there are two elements from two distinct Binary Search Trees (BSTs) that add up to a given target value. Here’s a breakdown of the code implementation:
Define two iterators,
InorderMorrisTraversalandReverseInorderMorrisTraversal, utilizing the Morris Traversal technique for accessing BST elements in order and reverse order, respectively. Both iterators work without additional memory, making them space efficient.The
InorderMorrisTraversalclass provides normal in-order traversal of a binary tree where left nodes are visited first, followed by the current node, and then right nodes.Conversely, the
ReverseInorderMorrisTraversalclass traverses the tree in the reverse in-order, starting with right nodes, then visiting the current node, and finishing with left nodes.Each traversal class implements two primary methods,
hasNext()to check if more nodes are left to visit, andnext()to access the next node value. Thenext()method modifies the tree temporarily to avoid using auxiliary space for maintaining traversal state.In the
Solutionclass, instantiate both iterators with separate root nodes of the two BSTs. Then, proceed with a two-pointer technique:- Initialize pointers using the first values from both iterators.
- If their sum matches the target, return true.
- If their sum is less than the target, move the pointer from
InorderMorrisTraversalto potentially get a higher value. - If the sum is greater, move the pointer from
ReverseInorderMorrisTraversalto get a lower value. - Continue this process until all possibilities are exhausted.
The loop terminates when either one of the iterators runs out of elements, indicated by both pointers reaching
Integer.MIN_VALUE.
This solution is notable for its efficient use of space, leveraging Morris Traversal to avoid extra space complexity that would typically result from using stack for tree traversal. It smartly combines in-order and reverse in-order traversals to systematically check pairs across the two BSTs against the target sum.
- Python
# Binary tree node definition
# class TreeNode:
# def __init__(self, value=0, left_child=None, right_child=None):
# self.value = value
# self.left = left_child
# self.right = right_child
class Solution:
def checkTwoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def inorder_traversal(root):
node = root
while node:
if not node.left:
yield node.value
node = node.right
else:
predecessor = node.left
while predecessor.right and predecessor.right != node:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = node
node = node.left
else:
predecessor.right = None
yield node.value
node = node.right
def reverse_inorder_traversal(root):
node = root
while node:
if not node.right:
yield node.value
node = node.left
else:
successor = node.right
while successor.left and successor.left != node:
successor = successor.left
if not successor.left:
successor.left = node
node = node.right
else:
successor.left = None
yield node.value
node = node.left
it1 = inorder_traversal(root1)
it2 = reverse_inorder_traversal(root2)
next1 = next(it1, None)
next2 = next(it2, None)
while next1 is not None and next2 is not None:
current_sum = next1 + next2
if current_sum == target:
return True
elif current_sum < target:
next1 = next(it1, None)
else:
next2 = next(it2, None)
return False
This Python code defines a solution to determine if two Binary Search Trees (BSTs) contain any two elements that when summed together equal a given target number. Here's a breakdown of how the solution operates:
TreeNode Structure: A class
TreeNodeis assumed to be defined, representing the node in a binary tree with attributes for its value, left child, and right child.Solution Class and Function:
- Inside the
Solutionclass, the functioncheckTwoSumBSTsaccepts three parameters:root1,root2representing the roots of the two BSTs, andtarget, the integer sum to find.
- Inside the
Inorder and Reverse Inorder Traversals:
- The function defines
inorder_traversal, which yields nodes' values of a BST in ascending order using an iterative approach to reduce stack overhead. reverse_inorder_traversalyields nodes' values in descending order.
- The function defines
Iterative Comparison:
- With iterators
it1andit2from theinorder_traversalofroot1andreverse_inorder_traversalofroot2respectively, the algorithm iteratively retrieves elements from both trees. - It sums the retrieved elements (
next1andnext2). If the sum equals the target, it directly returnsTrue. - If the sum is less than the target, it advances the
inorder_traversalto potentially get a larger value. If the sum is greater, it advances thereverse_inorder_traversalto potentially get a smaller value.
- With iterators
Termination:
- The loop terminates when elements from either tree are exhausted (
next1ornext2isNone), and if no matching pair is found, it returnsFalse.
- The loop terminates when elements from either tree are exhausted (
This solution efficiently checks for two number sum in two BSTs without transforming them entirely into arrays, leveraging the properties of in-order and reverse in-order traversals to search for the target sum efficiently. This makes it handle large structures relatively quickly compared to naive approaches.
No comments yet.