Find a pair with a given sum in BST

Problem Overview

In this problem, we are given a binary search tree (BST) and an integer k. Our task is to determine whether there exists two distinct elements a and b in the BST such that a + b = k. This problem is an extension to the classic "Two Sum" problem but with the input presented in the form of a BST.

Understanding the Problem

Given a BST, we need to find two different nodes whose values add up to a given integer k. The binary search tree property is crucial here, as it provides an efficient way to search for elements. We need to handle distinct elements; thus, we can't use the same value from the node to sum up with itself.

Key DSA Concepts and Theory

Binary Search Tree

A Binary Search Tree is a binary tree where each node follows the properties:

• Left subtree nodes are less than the node’s value.
• Right subtree nodes are greater than the node’s value.

This property makes it efficient to search for an element in O(log n) time on average, where n is the number of nodes in the tree.

In-order Traversal

To leverage the BST properties, in-order traversal is used, which processes nodes in non-decreasing order. This traversal strategy is crucial for some solution approaches, such as the two-pointer technique.

Two-Pointer Technique

Two-pointer technique involves having two indices starting from both ends of a sorted data structure. The sum of values at these indices can be compared with the target, adjusting the pointers based on the comparison, which is typically more efficient than a double iteration.

Solution Approach

Here's a detailed step-by-step solution utilizing a DFS traversal to gather the BST elements and then using the two-pointer technique:

Approach 1: Using DFS and HashSet

1. Perform In-order Traversal: Traverse the tree and collect the values in a list.
2. Use Two-Pointer Technique: Since the list from the in-order traversal is sorted, use two pointers to find if there exists a pair that sums up to k.

C++ Code Example

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> seen;
        return dfs(root, k, seen);
    }
    
private:
    bool dfs(TreeNode* node, int k, unordered_set<int> &seen) {
        if (!node) return false;
        if (seen.count(k - node->val)) return true;
        seen.insert(node->val);
        return dfs(node->left, k, seen) || dfs(node->right, k, seen);
    }
};

Java Code Example

import java.util.HashSet;
import java.util.Set;

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        return dfs(root, k, seen);
    }
    
    private boolean dfs(TreeNode node, int k, Set<Integer> seen) {
        if (node == null) return false;
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left, k, seen) || dfs(node.right, k, seen);
    }
}

Time and Space Complexity Analysis

Time Complexity

• In-order Traversal and Set Check: O(n), where n is the number of nodes since each node is visited once.

Space Complexity

• Space for Set/HashMap: O(n) in the worst case, for storing each node value once, which may occur in an unbalanced tree.

Common Mistakes to Avoid

• Reusing the Same Node: Ensure that a node's value is not reused to sum up with itself unless there are duplicate values in different nodes.
• Failing to Utilize BST Properties: Given it’s a BST, use sorted order properties to optimize your solution.

Similar Problems on LeetCode

• Two Sum: LeetCode 1
• Find a Corresponding Node of a Binary Tree in a Clone of That Tree: LeetCode 1379
• Convert Sorted Array to Binary Search Tree: LeetCode 108

Additional Resources and References

• Binary Search Tree Wikipedia
• In-order Traversal Explanation
• Two Pointer Technique
• LeetCode Discussions and Solutions

This detailed explanation and solution approach provides a comprehensive guide on approaching and solving the Two Sum IV problem using a BST efficiently.