Two Sum BSTs
Medium · Graphs · Explanation and code example
Morris Traversal
How it works
The two-pointer approach requires O(m + n) space to store the sorted lists. Morris traversal lets us iterate through a BST in sorted order using O(1) extra space by temporarily modifying tree pointers. We use forward Morris traversal on one tree and reverse Morris traversal on the other to simulate the two-pointer technique without extra space.
Steps
- Create a forward Morris iterator for the first tree (yields values in ascending order).
- Create a reverse Morris iterator for the second tree (yields values in descending order).
- Get the first value from each iterator.
- While both values are valid:
- If sum equals
target, returntrue. - If sum is less than
target, advance the forward iterator. - If sum is greater than
target, advance the reverse iterator.
- If sum equals
- Return
falseif no pair is found.
Complexity
- Time complexity:
O(m + n) - Space complexity:
O(1)
Where
mandnare the number of nodes in the two trees.
Things to watch for
Treating the Trees as Regular Binary Trees
A common mistake is ignoring the BST property and treating both trees as generic binary trees. This leads to inefficient solutions that don't leverage the sorted structure for binary search or two-pointer approaches. Always consider whether the BST ordering can help optimize your search.
Computing the Complement Incorrectly
When searching for a pair that sums to the target, some forget to compute target - value correctly or accidentally search for the wrong value. For example, if target = 9 and the current node has value 4, you need to search for 5 in the other tree, not 9 - 4 = 5 with any other formula.
Modifying Tree Structure with Morris Traversal
Morris traversal temporarily modifies tree pointers to achieve O(1) space. A pitfall is forgetting to restore the original tree structure after traversal or exiting early without cleanup. This can corrupt the tree for subsequent operations or cause infinite loops.
Python code example
from typing import Optional
class Solution:
def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
def morris_traversal(root):
current = root
while current:
if not current.left:
yield current.val
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
yield current.val
current = current.right
def reversed_morris_traversal(root):
current = root
while current:
if not current.right:
yield current.val
current = current.left
else:
pre = current.right
while pre.left and pre.left != current:
pre = pre.left
if not pre.left:
pre.left = current
current = current.right
else:
pre.left = None
yield current.val
current = current.left
iterater1 = morris_traversal(root1)
iterater2 = reversed_morris_traversal(root2)
value1 = next(iterater1, None)
value2 = next(iterater2, None)
while value1 is not None and value2 is not None:
if value1 + value2 == target:
return True
elif value1 + value2 < target:
value1 = next(iterater1, None)
else:
value2 = next(iterater2, None)
return False
C++ code example
class MorrisIterator {
private:
TreeNode* current;
TreeNode* pre;
public:
MorrisIterator(TreeNode* root) : current(root), pre(nullptr) {}
bool hasNext() {
return current != nullptr;
}
int next() {
int val = INT_MIN;
while (current != nullptr) {
if (current->left == nullptr) {
val = current->val;
current = current->right;
break;
} else {
pre = current->left;
while (pre->right != nullptr && pre->right != current) {
pre = pre->right;
}
if (pre->right == nullptr) {
pre->right = current;
current = current->left;
} else {
pre->right = nullptr;
val = current->val;
current = current->right;
break;
}
}
}
return val;
}
};
class ReversedMorrisIterator {
private:
TreeNode* current;
TreeNode* pre;
public:
ReversedMorrisIterator(TreeNode* root) : current(root), pre(nullptr) {}
bool hasNext() {
return current != nullptr;
}
int next() {
int val = INT_MIN;
while (current != nullptr) {
if (current->right == nullptr) {
val = current->val;
current = current->left;
break;
} else {
pre = current->right;
while (pre->left != nullptr && pre->left != current) {
pre = pre->left;
}
if (pre->left == nullptr) {
pre->left = current;
current = current->right;
} else {
pre->left = nullptr;
val = current->val;
current = current->left;
break;
}
}
}
return val;
}
};
class Solution {
public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
MorrisIterator iterator1(root1);
ReversedMorrisIterator iterator2(root2);
int value1 = iterator1.next();
int value2 = iterator2.next();
while (value1 != INT_MIN && value2 != INT_MIN) {
if (value1 + value2 == target) {
return true;
} else if (value1 + value2 < target) {
if (iterator1.hasNext()) {
value1 = iterator1.next();
} else {
value1 = INT_MIN;
}
} else {
if (iterator2.hasNext()) {
value2 = iterator2.next();
} else {
value2 = INT_MIN;
}
}
}
return false;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.