Algorithms to Check Sum of Two Numbers in Binary Search Trees

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).

/**
 * 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.

/**
 * 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) —