DSA 450 Notes

Problem Statement

Given two BSTs containing n1 and n2 distinct nodes respectively, count the number of pairs (one from each BST) whose sum equals a given value x.

Example:

BST 1:          BST 2:
    5               6
   / \             / \
  3   7           4   8
 / \             / \
1   4           2   5

x = 10
Output: 3
Pairs: (5,5), (3,7) - wait, 7 is in BST1 not BST2
Actually: (4,6), (5,5), (2,8) - checking sums equal to 10
Pairs: (5,5)=10, (4,6)=10, (2,8)=10

Approach 1: Brute Force (Two Nested Traversals)

Intuition

For each node in BST1, search for (x - node.val) in BST2.

Algorithm

Traverse all nodes in BST1
For each node, search for complement (x - val) in BST2
Count successful finds

java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private boolean searchBST(TreeNode root, int target) {
        if (root == null) return false;
        if (root.val == target) return true;
        if (target < root.val) return searchBST(root.left, target);
        return searchBST(root.right, target);
    }
    
    private int count = 0;
    
    private void countPairsHelper(TreeNode root1, TreeNode root2, int x) {
        if (root1 == null) return;
        
        // Check if complement exists in BST2
        if (searchBST(root2, x - root1.val)) {
            count++;
        }
        
        countPairsHelper(root1.left, root2, x);
        countPairsHelper(root1.right, root2, x);
    }
    
    public int countPairs(TreeNode root1, TreeNode root2, int x) {
        count = 0;
        countPairsHelper(root1, root2, x);
        return count;
    }
}

Complexity Analysis

Time Complexity: O(m * n) or O(m * h2) - For each of m nodes, search in BST2
Space Complexity: O(h1 + h2) - Recursion stacks

Approach 2: Better (Using HashSet)

Intuition

Store all values from one BST in a HashSet. For each node in the other BST, check if complement exists in the set.

Algorithm

Traverse BST1 and store all values in HashSet
Traverse BST2 and check if (x - val) exists in HashSet
Count matches

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void storeInorder(TreeNode root, Set<Integer> set) {
        if (root == null) return;
        storeInorder(root.left, set);
        set.add(root.val);
        storeInorder(root.right, set);
    }
    
    private int countWithSet(TreeNode root, Set<Integer> set, int x) {
        if (root == null) return 0;
        
        int count = set.contains(x - root.val) ? 1 : 0;
        
        return count + countWithSet(root.left, set, x) + countWithSet(root.right, set, x);
    }
    
    public int countPairsHashSet(TreeNode root1, TreeNode root2, int x) {
        Set<Integer> set = new HashSet<>();
        storeInorder(root1, set);
        return countWithSet(root2, set, x);
    }
}

Complexity Analysis

Time Complexity: O(m + n) - Linear traversal of both trees
Space Complexity: O(m) or O(n) - HashSet storage

Approach 3: Optimal (Two Pointer with BST Iterators)

Intuition

Use two pointers technique similar to finding pairs in sorted arrays. Use BST iterators - one going forward (smallest to largest) on BST1 and one going backward (largest to smallest) on BST2.

Algorithm

Create forward iterator for BST1 (inorder)
Create backward iterator for BST2 (reverse inorder)
Use two pointers: if sum < x, move forward; if sum > x, move backward
Count when sum equals x

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class BSTIterator {
    private Stack<TreeNode> stack;
    private boolean reverse;
    
    public BSTIterator(TreeNode root, boolean isReverse) {
        stack = new Stack<>();
        reverse = isReverse;
        pushAll(root);
    }
    
    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = reverse ? node.right : node.left;
        }
    }
    
    public int next() {
        TreeNode curr = stack.pop();
        pushAll(reverse ? curr.left : curr.right);
        return curr.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

public class Solution {
    public int countPairsOptimal(TreeNode root1, TreeNode root2, int x) {
        if (root1 == null || root2 == null) return 0;
        
        BSTIterator iter1 = new BSTIterator(root1, false);
        BSTIterator iter2 = new BSTIterator(root2, true);
        
        int count = 0;
        int val1 = iter1.next();
        int val2 = iter2.next();
        
        while (true) {
            int sum = val1 + val2;
            
            if (sum == x) {
                count++;
                if (!iter1.hasNext() || !iter2.hasNext()) break;
                val1 = iter1.next();
                val2 = iter2.next();
            } else if (sum < x) {
                if (!iter1.hasNext()) break;
                val1 = iter1.next();
            } else {
                if (!iter2.hasNext()) break;
                val2 = iter2.next();
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(m + n) - Each node visited at most once
Space Complexity: O(h1 + h2) - Stack space for iterators

Key Takeaways

Two pointer technique: Apply to BSTs using iterators
BST Iterator: Powerful pattern for BST problems
Forward + Backward: Mimics sorted array two-pointer approach
HashSet trade-off: O(m+n) time but O(m) or O(n) space
Optimal approach uses only O(h1+h2) space
Similar pattern for finding pair with given sum in single BST
Can be extended to count pairs with sum in a range

Count pairs from 2 BST whose sum is equal to given value X

Problem Statement

Approach 1: Brute Force (Two Nested Traversals)

Intuition

Algorithm

Complexity Analysis

Approach 2: Better (Using HashSet)

Intuition

Algorithm

Complexity Analysis

Approach 3: Optimal (Two Pointer with BST Iterators)

Intuition

Algorithm

Complexity Analysis

Key Takeaways