Why Two Sum in BST in DSA C?

The Big Idea

What if you could find two numbers adding to your target in a tree without checking every pair?

The Scenario

Imagine you have a large family photo album sorted by year, and you want to find two photos whose years add up to a special number. You try flipping through pages one by one, checking every possible pair manually.

The Problem

This manual search is slow and tiring because you must check many pairs, often repeating checks. It's easy to miss pairs or waste time on unnecessary comparisons, especially if the album is huge.

The Solution

Using a Binary Search Tree (BST) and the Two Sum approach, you can quickly find if two numbers add up to the target by smartly navigating the tree. This avoids checking every pair and speeds up the search.

Before vs After

✗ Before

for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    if (arr[i] + arr[j] == target) return true;
  }
}

✓ After

bool findTwoSumBST(Node* root, int target) {
  // Use BST properties and two-pointer technique
  // to find if two nodes sum to target
  return false; // placeholder
}

What It Enables

This concept enables fast and efficient searching for pairs in sorted tree data, making complex queries simple and quick.

Real Life Example

Finding two expenses in a sorted list of transactions that add up to a suspicious amount during an audit.

Key Takeaways

Manual pair checking is slow and error-prone.

BST structure helps navigate data efficiently.

Two Sum in BST finds pairs quickly without checking all combinations.

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Check if the BST is balanced.

B. Find the maximum value in the BST.

C. Find two nodes in the BST whose values add up to a given target sum.

D. Count the total number of nodes in the BST.

Solution

1. Step 1: Understand the problem requirement

   The problem asks to find two nodes in the BST such that their values add up to a target sum.

2. Step 2: Identify the correct goal

   Among the options, only finding two nodes with values summing to the target matches the problem.

3. Final Answer:

   Find two nodes in the BST whose values add up to a given target sum. -> Option C

4. Quick Check:

   Two Sum in BST = Find two nodes summing to target [OK]

Hint: Look for pairs adding to target in BST [OK]

Common Mistakes:

• Confusing with finding max/min value
• Thinking it's about counting nodes
• Assuming it's about tree balance

2. Which of the following is the correct way to declare a function in C that checks for two sum in a BST?

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

easy

A. void findTwoSum(struct TreeNode root, int target);

B. int findTwoSum(struct TreeNode* root, int* target);

C. int findTwoSum(struct TreeNode root, int target);

D. int findTwoSum(struct TreeNode* root, int target);

Solution

1. Step 1: Check function parameter types

   The BST root should be passed as a pointer to struct TreeNode, and target as int.

2. Step 2: Verify return type and parameters

   int findTwoSum(struct TreeNode* root, int target); correctly declares return type int, pointer to root, and int target.

3. Final Answer:

   int findTwoSum(struct TreeNode* root, int target); -> Option D

4. Quick Check:

   Function signature with pointer root and int target = int findTwoSum(struct TreeNode* root, int target); [OK]

Hint: Use pointer for tree root in function parameters [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using void return type when int is needed
• Passing target as pointer unnecessarily

3. What will be the output of the following code snippet?

// BST nodes: 5, 3, 6, 2, 4, 7
// Target sum = 9

int main() {
    // Assume createBST() creates the BST with given nodes
    struct TreeNode* root = createBST();
    int target = 9;
    int result = findTwoSum(root, target);
    printf("%d\n", result);
    return 0;
}

// findTwoSum returns 1 if pair found, else 0

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Identify pairs in BST that sum to target

   Pairs like (2,7) and (3,6) sum to 9 in the BST.

2. Step 2: Check if findTwoSum returns 1 when pair exists

   Since pairs exist, function returns 1 and prints it.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Pair found = 1 [OK]

Hint: Check if any two nodes sum to target [OK]

Common Mistakes:

• Assuming no pairs exist
• Confusing return values
• Ignoring BST structure

4. Identify the bug in the following code snippet for Two Sum in BST:

int findTwoSum(struct TreeNode* root, int target) {
    if (!root) return 0;
    int complement = target - root->val;
    if (searchBST(root, complement)) {
        return 1;
    }
    return findTwoSum(root->left, target) || findTwoSum(root->right, target);
}

// searchBST searches for a value in BST

medium

A. It uses wrong target value in recursion.

B. It may count the same node twice as complement.

C. It does not check if root is NULL.

D. It misses checking the left subtree.

Solution

1. Step 1: Analyze complement calculation and search

   The code searches for complement in the whole tree including current node.

2. Step 2: Identify issue with counting same node twice

   If complement equals root->val, it may count the same node twice incorrectly.

3. Final Answer:

   It may count the same node twice as complement. -> Option B

4. Quick Check:

   Same node counted twice bug = It may count the same node twice as complement. [OK]

Hint: Avoid counting current node as complement [OK]

Common Mistakes:

• Not excluding current node in search
• Ignoring NULL checks
• Wrong recursion parameters

5. Given a BST with nodes [10, 5, 15, 3, 7, 18] and target sum 22, which pair of nodes will the Two Sum in BST algorithm find first if it uses in-order traversal and a hash set to track visited values?

hard

A. (7, 15)

B. (5, 17)

C. (3, 19)

D. (10, 12)

Solution

1. Step 1: Perform in-order traversal and track visited nodes

   In-order traversal visits nodes in order: 3, 5, 7, 10, 15, 18.

2. Step 2: Check pairs summing to 22 using hash set

   Process nodes in order: visit 3 (add 3), 5 (add 5), 7 (add 7), 10 (add 10), 15 (complement 7 is in set), so first pair found is (7,15).

3. Final Answer:

   (7, 15) -> Option A

4. Quick Check:

   In-order + hash set finds (7,15) first [OK]

Hint: Use in-order + hash set to find pairs fast [OK]

Common Mistakes:

• Assuming pairs with non-existent nodes
• Ignoring traversal order
• Mixing node values incorrectly