Pair Sum in BST

Given a Binary Search Tree(BST) and a target. Check whether there’s a pair of Nodes in the BST with value summing up to the target. 

Examples:

Input: root = [7, 3, 8, 2, 4, N, 9], target = 12
       
Output: True
Explanation: In the binary tree above, there are two nodes (8 and 4) that add up to 12.

Input: root = [9, 5, 10, 2, 6, N, 12], target = 23
          
Output: False
Explanation: In the binary tree above, there are no such two nodes exists that add up to 23.

Constraints:

1 ≤ Number of Nodes ≤ 10⁵
1 ≤ target ≤ 10⁶

Approach 01:

#include <unordered_map>

class Solution {
  public:
    std::unordered_map<int, int> valueMap;

    bool findTarget(Node* root, int target) {
        if (!root) 
            return false;

        int currentValue = root->data;

        // Check if complement (target - currentValue) exists in the map
        if (valueMap.find(target - currentValue) != valueMap.end()) 
            return true;

        // Store the current value in the map
        valueMap[currentValue]++;

        // Search in left and right subtrees
        return findTarget(root->left, target) || findTarget(root->right, target);
    }
};

class Solution:
    def __init__(self):
        self.valueMap = {}

    def findTarget(self, root, target):
        if not root:
            return False

        currentValue = root.data

        # Check if complement (target - currentValue) exists in the map
        if (target - currentValue) in self.valueMap:
            return True

        # Store the current value in the map
        self.valueMap[currentValue] = self.valueMap.get(currentValue, 0) + 1

        # Search in left and right subtrees
        return self.findTarget(root.left, target) or self.findTarget(root.right, target)

Time Complexity:

• Tree Traversal:

  We perform a DFS traversal, visiting each node once, leading to \( O(N) \) time complexity.

• Map Lookup and Insertion:

  Each lookup and insertion operation in an unordered_map takes \( O(1) \) on average.

• Overall Time Complexity:

  \( O(N) \) since each node is processed once.

Space Complexity:

• Hash Map Storage:

  In the worst case, we store all \( N \) node values in the unordered_map, leading to \( O(N) \) space complexity.

• Recursive Stack:

  For a skewed tree, the recursion depth reaches \( O(N) \), while for a balanced tree, it is \( O(\log N) \).

• Overall Space Complexity:

  Worst case: \( O(N) \), Best case: \( O(\log N) \).