Problem Overview

Given two binary search trees and a target sum, find all unique pairs of values (one from each tree) that add up to the target. This requires efficient traversal and searching techniques to handle large datasets within time constraints.

Inefficient Approach (O(n²) complexity)

The first approach involves traversing the first tree in-order to get sorted values, then for each value, searching in the second tree and checking for duplicates in the result array:

int locateValue(TreeNode* node, int target_value) {
    if (!node) return 0;
    
    if (target_value == node->val) return 1;
    if (target_value > node->val) {
        return locateValue(node->right, target_value);
    }
    return locateValue(node->left, target_value);
}

int computeSums(TreeNode *tree1, TreeNode *tree2, int target_sum, int result_x[], int result_y[]) {
    TreeNode* traversal_stack[99999];
    int stack_top = -1, count = 0, temp_idx = 0, duplicate_check;
    TreeNode *current = tree1;
    
    while (current || stack_top != -1) {
        while (current) {
            traversal_stack[++stack_top] = current;
            current = current->left;
        }
        current = traversal_stack[stack_top--];
        
        duplicate_check = 1;
        for (temp_idx = 0; temp_idx < count; temp_idx++) {
            if (result_x[temp_idx] == current->val) {
                duplicate_check = 0;
                break;
            }
        }
        
        if (duplicate_check && locateValue(tree2, target_sum - current->val)) {
            result_x[count] = current->val;
            result_y[count++] = target_sum - current->val;
        }
        current = current->right;
    }
    return count;
}

This method suffers from O(n²) time complexity due to repeated searches and duplicate checks, making it unsuitable for large datasets.

Optimized Approach (O(n) complexity)

The improved solution pre-processes the second tree into a sorted array, then uses a two-pointer-like technique during traversal of the first tree:

int computeSums(TreeNode *tree1, TreeNode *tree2, int target_sum, int result_x[], int result_y[]) {
    TreeNode* work_stack[99999];
    int stack_ptr = -1, second_tree_idx = -1, result_count = 0, is_duplicate;
    int second_values[99999];
    TreeNode *current = tree2;
    
    // Process second tree into sorted array
    while (current || stack_ptr != -1) {
        while (current) {
            work_stack[++stack_ptr] = current;
            current = current->left;
        }
        current = work_stack[stack_ptr--];
        second_values[++second_tree_idx] = current->val;
        current = current->right;
    }
    
    // Process first tree and match with second tree values
    current = tree1;
    while (current || stack_ptr != -1) {
        while (current) {
            work_stack[++stack_ptr] = current;
            current = current->left;
        }
        current = work_stack[stack_ptr--];
        
        // Check for duplicates with previous result
        if ((result_count == 0) || (result_count > 0 && result_x[result_count-1] != current->val)) {
            is_duplicate = 0;
            
            // Navigate through second tree values from end
            while (second_tree_idx >= 0) {
                if (second_values[second_tree_idx] + current->val >= target_sum) {
                    if (second_values[second_tree_idx] + current->val == target_sum) {
                        is_duplicate = 1;
                        break;
                    } else {
                        second_tree_idx--; // Move backward in second tree
                    }
                } else {
                    break; // Sum too small, exit loop
                }
            }
            
            if (is_duplicate) {
                result_x[result_count] = current->val;
                result_y[result_count++] = target_sum - current->val;
            }
            
            if (second_tree_idx < 0) break; // Second tree exhausted
        }
        current = current->right;
    }
    return result_count;
}

This optimized approach reduces complexity to approximately O(2n) by eliminating redundant searches and using pre-sorted data structures. The algorithm processes both trees in-order to maintain sorted sequences, then efficiently matches pairs usinng a pointer-based approach.