Two Sum in BST in DSA C++

Mental Model

We want to find two numbers in a tree that add up to a target. We use the tree's order to check pairs efficiently.

Analogy: Imagine a sorted list of prices in a store. You want to find two items that together cost exactly your budget. Instead of checking all pairs, you look from the cheapest and the most expensive items moving inward.

    5
   / \
  3   7
 / \   \
2   4   8

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, target = 9

Goal: Find if there exist two nodes in BST whose values sum to 9

Step 1: Initialize two pointers: left at smallest (2), right at largest (8)

left=2, right=8

Why: Start checking pairs from smallest and largest values

Step 2: Sum left + right = 2 + 8 = 10, which is greater than target 9

left=2, right=8

Why: Sum too big, move right pointer to next smaller value

Step 3: Move right pointer from 8 to 7

left=2, right=7

Why: Try smaller value to reduce sum

Step 4: Sum left + right = 2 + 7 = 9, equals target

left=2, right=7

Why: Found two nodes that sum to target

Result:

2 -> ... -> 7 -> ... (found pair 2 and 7 that sum to 9)

Annotated Code

DSA C++

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BSTIterator {
    stack<TreeNode*> st;
    bool forward;
public:
    BSTIterator(TreeNode* root, bool isForward) : forward(isForward) {
        pushAll(root);
    }
    
    bool hasNext() {
        return !st.empty();
    }
    
    int next() {
        TreeNode* node = st.top();
        st.pop();
        if (forward) pushAll(node->right);
        else pushAll(node->left);
        return node->val;
    }
private:
    void pushAll(TreeNode* node) {
        while (node) {
            st.push(node);
            node = forward ? node->left : node->right;
        }
    }
};

bool findTarget(TreeNode* root, int k) {
    if (!root) return false;
    BSTIterator leftIt(root, true);  // smallest to largest
    BSTIterator rightIt(root, false); // largest to smallest

    int i = leftIt.next();
    int j = rightIt.next();

    while (i < j) {
        int sum = i + j;
        if (sum == k) return true;
        else if (sum < k) {
            if (leftIt.hasNext()) i = leftIt.next();
            else break;
        } else {
            if (rightIt.hasNext()) j = rightIt.next();
            else break;
        }
    }
    return false;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(8);

    int target = 9;
    bool found = findTarget(root, target);
    cout << (found ? "Found pair summing to " : "No pair found for ") << target << endl;
    return 0;
}

BSTIterator leftIt(root, true); // smallest to largest

initialize iterator to get next smallest values

BSTIterator rightIt(root, false); // largest to smallest

initialize iterator to get next largest values

int i = leftIt.next();

get smallest value from BST

int j = rightIt.next();

get largest value from BST

while (i < j) {

loop until pointers cross

int sum = i + j;

calculate sum of current pair

if (sum == k) return true;

found pair that sums to target

else if (sum < k) i = leftIt.next();

sum too small, move left pointer forward

else j = rightIt.next();

sum too big, move right pointer backward

Output

Found pair summing to 9

Complexity Analysis

Time: O(n) because in worst case we may visit all nodes once with two iterators

Space: O(h) where h is tree height due to stack space in iterators

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST order to reduce to O(n)

Edge Cases

Empty tree

Returns false immediately, no pairs to check

DSA C++

if (!root) return false;

Single node tree

No pair exists, returns false

DSA C++

while (i < j) { ... } ensures no false positives

No two nodes sum to target

Iterators cross without finding pair, returns false

DSA C++

while (i < j) loop ends and returns false

When to Use This Pattern

When asked to find two elements in a BST that sum to a target, use two iterators moving inward from smallest and largest values to find the pair efficiently.

Common Mistakes

Mistake: Using a single traversal and checking pairs without BST order, causing O(n^2) time
Fix: Use two iterators from smallest and largest to leverage BST order and reduce time to O(n)

Mistake: Not handling the case when iterators cross, leading to infinite loop
Fix: Stop loop when left pointer value is not less than right pointer value

Summary

Finds if two nodes in a BST sum to a given target using two-pointer technique with BST iterators.

Use when you need to find a pair sum efficiently in a BST without extra space for arrays.

The key insight is to use two iterators moving from smallest and largest values inward to find the sum.

Practice

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

easy

A. Find the maximum value in a BST

B. Find two nodes in a BST whose values add up to a target sum

C. Count the number of nodes in a BST

D. Check if a BST is balanced

Solution

1. Step 1: Understand the problem statement

   The problem asks to find if there exist two nodes in a Binary Search Tree (BST) such that their values add up to a given target sum.

2. Step 2: Identify the goal

   The goal is to check for the existence of such a pair, not to find maximum, count nodes, or check balance.

3. Final Answer:

   Find two nodes in a BST whose values add up to a target sum -> Option B

4. Quick Check:

   Two Sum in BST means finding two nodes summing to target [OK]

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

Common Mistakes:

• Confusing with finding max/min value
• Thinking it counts nodes instead of pairs
• Assuming it checks tree balance

2. Which of the following C++ code snippets correctly declares a BST node structure for the Two Sum problem?

easy

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

B. struct TreeNode { int val; TreeNode left; TreeNode right; };

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

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

Solution

1. Step 1: Check pointer usage in struct

   In C++, child nodes in a tree are pointers to TreeNode objects, so left and right must be pointers.

2. Step 2: Validate each option

   struct TreeNode { int val; TreeNode* left; TreeNode* right; }; uses TreeNode* for left and right, which is correct. Options A, B, and C incorrectly use TreeNode without pointers for one or both children.

3. Final Answer:

   struct TreeNode { int val; TreeNode* left; TreeNode* right; }; -> Option C

4. Quick Check:

   BST nodes use pointers for children [OK]

Hint: Children in BST nodes are pointers in C++ [OK]

Common Mistakes:

• Using objects instead of pointers for children
• Mixing pointer and non-pointer types
• Forgetting semicolon after struct

3. What is the output of the following code snippet that checks for two sum in BST?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool findTarget(TreeNode* root, int k) {
  std::unordered_set<int> seen;
  std::function dfs = [&](TreeNode* node) {
    if (!node) return false;
    if (seen.count(k - node->val)) return true;
    seen.insert(node->val);
    return dfs(node->left) || dfs(node->right);
  };
  return dfs(root);
}

int main() {
  TreeNode* root = new TreeNode(5);
  root->left = new TreeNode(3);
  root->right = new TreeNode(6);
  root->left->left = new TreeNode(2);
  root->left->right = new TreeNode(4);
  root->right->right = new TreeNode(7);
  
  bool result = findTarget(root, 9);
  std::cout << (result ? "true" : "false") << std::endl;
  return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand the tree and target

   The BST has nodes 5,3,6,2,4,7. The target sum is 9.

2. Step 2: Trace the DFS and set usage

   DFS visits nodes and checks if (target - current node value) is in the set. For example, when visiting node 6, it checks if 9-6=3 is in set. Node 3 was visited before, so it returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   3 + 6 = 9 found in BST [OK]

Hint: Check if complement exists in visited nodes set [OK]

Common Mistakes:

• Assuming no pair exists without checking all nodes
• Confusing DFS order with BFS
• Ignoring the use of hash set for complements

4. Identify the bug in the following Two Sum in BST code snippet and select the correct fix:

bool findTarget(TreeNode* root, int k) {
  std::unordered_set<int> seen;
  std::function dfs = [&](TreeNode* node) {
    if (!node) return false;
    if (seen.count(k - node->val)) return true;
    dfs(node->left);
    dfs(node->right);
    seen.insert(node->val);
    return false;
  };
  return dfs(root);
}

medium

A. Insert node->val before recursive calls to children

B. Remove the unordered_set and use a vector instead

C. Change return false to return true at the end

D. Add a null check after inserting node->val

Solution

1. Step 1: Analyze the order of operations

   The code inserts node->val into the set after recursive calls, so complements are not found when visiting children.

2. Step 2: Fix the insertion timing

   Insert node->val before recursive calls so that children can find complements in the set.

3. Final Answer:

   Insert node->val before recursive calls to children -> Option A

4. Quick Check:

   Insert before recursion to find complements [OK]

Hint: Insert current value before recursion to detect complements [OK]

Common Mistakes:

• Inserting after recursion causes missed pairs
• Changing return values incorrectly
• Replacing set with vector reduces efficiency

5. Given a BST with nodes [10, 5, 15, 3, 7, null, 18], how would you modify the Two Sum in BST algorithm to handle the case where the target sum is twice the value of a single node (e.g., target = 14 and node value = 7)?

hard

A. Only check leaf nodes for pairs

B. Ignore pairs where complement equals current node value

C. Use a sorted array instead of a hash set

D. Check if the complement equals the current node value and ensure the node appears twice

Solution

1. Step 1: Understand the problem with duplicates

   If target is twice a node's value, we must ensure two distinct nodes with that value exist.

2. Step 2: Modify algorithm to handle duplicates

   When complement equals current node value, check if the node appears twice (e.g., by counting occurrences or checking different nodes).

3. Final Answer:

   Check if the complement equals the current node value and ensure the node appears twice -> Option D

4. Quick Check:

   Handle duplicates by verifying two distinct nodes [OK]

Hint: Verify two distinct nodes if complement equals current value [OK]

Common Mistakes:

• Ignoring duplicate values causing false positives
• Skipping pairs with same node value
• Switching data structures unnecessarily