You are given two binary search trees a and b and an integer target. Return whether there’s a number in a and a number in b such that their sum equals to target
Constraints
n ≤ 100,000 where n is the number of nodes in a
m ≤ 100,000 where m is the number of nodes in b
Recursive Algorithm to Find Sum of Two Numbers in BSTs
If the target is found by summing the two nodes in the current two trees A and B, great, return immediately. Otherwise, if the sum is bigger than the target, we can reduce the sum by either moving A to its left or B to its left. Similarly if the sum is smaller than the target, we can increase the sum by either moving A to its right or B to its right tree.
The complexity is O((logA*logB)^2). Space requirement is O(LogA+LogB).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ bool sumOfTwoNumberInBST(Tree* a, Tree* b, int target) { if (!a || !b) return false; if (a->val + b->val == target) return true; if (a->val + b->val < target) { return sumOfTwoNumberInBST(a->right, b, target) || sumOfTwoNumberInBST(a, b->right, target); } else { return sumOfTwoNumberInBST(a->left, b, target) || sumOfTwoNumberInBST(a, b->left, target); } } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
bool sumOfTwoNumberInBST(Tree* a, Tree* b, int target) {
if (!a || !b) return false;
if (a->val + b->val == target) return true;
if (a->val + b->val < target) {
return sumOfTwoNumberInBST(a->right, b, target) ||
sumOfTwoNumberInBST(a, b->right, target);
} else {
return sumOfTwoNumberInBST(a->left, b, target) ||
sumOfTwoNumberInBST(a, b->left, target);
}
}Binary Search Algorithm to Find Sum in Two Binary Search Trees
Binary Search Trees are suitable for “Binary Search”. We can traverse one tree say A, and search for (target – A) in Tree B. The complexity is O(ALogB) or O(BLogA) assuming both Binary Search Trees are highly balanced. As we are recursively traversing two trees, the space complexity is O(LogA+LogB) due to implicitly space from Recursion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * class Tree { * public: * int val; * Tree *left; * Tree *right; * }; */ bool sumOfTwoNumberInBST(Tree* a, Tree* b, int target) { function<bool(Tree*, int)> search = [](Tree* root, int target) { while (root) { if (target < root->val) { root = root->left; } else if (target > root->val) { root = root->right; } else { return true; } } return false; }; function<bool(Tree*)> dfs = [&](Tree* root) { if (!root) return false; if (search(b, target - root->val)) return true; if (dfs(root->left)) return true; if (dfs(root->right)) return true; return false; }; return dfs(a); } |
/**
* class Tree {
* public:
* int val;
* Tree *left;
* Tree *right;
* };
*/
bool sumOfTwoNumberInBST(Tree* a, Tree* b, int target) {
function<bool(Tree*, int)> search = [](Tree* root, int target) {
while (root) {
if (target < root->val) {
root = root->left;
} else if (target > root->val) {
root = root->right;
} else {
return true;
}
}
return false;
};
function<bool(Tree*)> dfs = [&](Tree* root) {
if (!root) return false;
if (search(b, target - root->val)) return true;
if (dfs(root->left)) return true;
if (dfs(root->right)) return true;
return false;
};
return dfs(a);
}See same algorithms that are implemented in Python: Teaching Kids Programming – Recursive Algorithm to Find the Sum of Two Numbers in BSTs
Two Sum Variation Problems
- Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
- Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
- Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
- Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
- Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
- Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
- Recursive and Two Pointer Algorithms to Determine Four Sum
- Algorithms to Check Sum of Two Numbers in Binary Search Trees
- Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
- How to Design a Two-Sum Data Structure?
- How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
- Teaching Kids Programming - Three Sum Algorithm
- Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
- Teaching Kids Programming – Two Sum Algorithm
- Two Pointer Algorithm to Find Maximum Two Sum Less Than K
- The Two Sum Algorithm using HashMap in C++/Java
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
Next Post: Simple Vigenère Cipher in C++
