Two Sum in BST in DSA C#

Mental Model

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

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

    5
   / \
  3   7
 / \   \
2   4   8

We want to find two nodes whose values add up to a target.

Dry Run Walkthrough

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

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

Step 1: Start with two pointers: one at smallest (2), one at largest (8)

2 ↑ -> 3 -> 4 -> 5 -> 7 -> 8 ↑

Why: We use the BST property to get smallest and largest values to check sums efficiently

Step 2: Sum 2 + 8 = 10, which is greater than 9, move the right pointer to next smaller (7)

2 ↑ -> 3 -> 4 -> 5 -> 7 ↑ -> 8

Why: Sum too big, so decrease the larger value to get closer to target

Step 3: Sum 2 + 7 = 9, equals target, pair found

2 ↑ -> 3 -> 4 -> 5 -> 7 ↑ -> 8

Why: Found two nodes that sum to target, stop search

Result:

2 -> 3 -> 4 -> 5 -> 7 -> 8
Pair found: 2 + 7 = 9

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    // Helper to get next smallest or largest value in BST iterator
    private class BSTIterator {
        private Stack<TreeNode> stack = new Stack<TreeNode>();
        private bool forward;

        public BSTIterator(TreeNode root, bool forward) {
            this.forward = forward;
            PushAll(root);
        }

        public bool HasNext() {
            return stack.Count > 0;
        }

        public int Next() {
            TreeNode node = stack.Pop();
            if (forward) PushAll(node.right);
            else PushAll(node.left);
            return node.val;
        }

        private void PushAll(TreeNode node) {
            while (node != null) {
                stack.Push(node);
                node = forward ? node.left : node.right;
            }
        }
    }

    public bool FindTarget(TreeNode root, int k) {
        if (root == null) return false;
        BSTIterator leftIter = new BSTIterator(root, true);  // smallest to largest
        BSTIterator rightIter = new BSTIterator(root, false); // largest to smallest

        int i = leftIter.Next();
        int j = rightIter.Next();

        while (i < j) {
            int sum = i + j;
            if (sum == k) return true;
            else if (sum < k) {
                if (leftIter.HasNext()) i = leftIter.Next();
                else break;
            } else {
                if (rightIter.HasNext()) j = rightIter.Next();
                else break;
            }
        }
        return false;
    }

    public static void Main() {
        TreeNode root = new TreeNode(5,
            new TreeNode(3,
                new TreeNode(2),
                new TreeNode(4)),
            new TreeNode(7,
                null,
                new TreeNode(8)));

        Solution sol = new Solution();
        bool found = sol.FindTarget(root, 9);
        Console.WriteLine(found ? "Pair found" : "No pair found");
    }
}

BSTIterator leftIter = new BSTIterator(root, true); // smallest to largest

Initialize iterator to get next smallest values

BSTIterator rightIter = new BSTIterator(root, false); // largest to smallest

Initialize iterator to get next largest values

int i = leftIter.Next();

Get smallest value from BST

int j = rightIter.Next();

Get largest value from BST

while (i < j) {

Loop until pointers cross, meaning all pairs checked

int sum = i + j;

Calculate sum of current pair

if (sum == k) return true;

If sum matches target, pair found

else if (sum < k) i = leftIter.Next();

Sum too small, move left pointer forward to increase sum

else j = rightIter.Next();

Sum too big, move right pointer backward to decrease sum

Output

Pair found

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 as no nodes exist

DSA C#

if (root == null) return false;

Single node tree

Returns false because we need two distinct nodes

DSA C#

while (i < j) { ... } ensures i and j are different

No pair sums to target

Returns false after exhausting all pairs

DSA C#

while (i < j) loop ends without return true

When to Use This Pattern

When asked to find two numbers in a BST that sum to a target, use two-pointer style iteration with BST iterators to efficiently find the pair.

Common Mistakes

Mistake: Trying to convert BST to array first, wasting extra space and time
Fix: Use BST iterators to traverse in order without full conversion

Mistake: Not handling the case when pointers cross, causing 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 target using two iterators from smallest and largest values.

Use when you need to check pairs in BST efficiently without extra space for full traversal.

The key insight is to use BST's sorted order to move two pointers inward like a sorted array.

Practice

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

easy

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

B. Find the maximum value in the BST.

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

D. Check if the BST is balanced.

Solution

1. Step 1: Understand the problem statement

   The problem asks to find 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 if such a pair exists, not to find max, count nodes, or check balance.

3. Final Answer:

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

4. Quick Check:

   Two Sum in BST = Find pair with target sum [OK]

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

Common Mistakes:

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

2. Which of the following C# method signatures is correct for a function that checks if two nodes in a BST sum to a target value?

easy

A. string FindTarget(TreeNode root, int target)

B. bool FindTarget(TreeNode root, int target)

C. void FindTarget(TreeNode root, int target)

D. int FindTarget(TreeNode root, int target)

Solution

1. Step 1: Understand the expected return type

   The function should return true or false depending on whether two nodes sum to the target, so return type must be bool.

2. Step 2: Check method signature options

   bool FindTarget(TreeNode root, int target) returns bool, matching the requirement. Others return int, void, or string, which are incorrect for this purpose.

3. Final Answer:

   bool FindTarget(TreeNode root, int target) -> Option B

4. Quick Check:

   Return type bool for true/false check [OK]

Hint: Function returns true/false, so use bool return type [OK]

Common Mistakes:

• Using void return type and expecting a result
• Returning int or string instead of bool
• Incorrect parameter types

3. Given the BST below and target = 9, what will the function FindTarget return?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. runtime error

B. false

C. null

D. true

Solution

1. Step 1: Identify pairs that sum to target 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All these pairs exist in the BST.

2. Step 2: Confirm function behavior

   Since at least one pair (e.g., 2 and 7) sums to 9, the function should return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Pair exists with sum 9 = true [OK]

Hint: Check all node pairs for target sum quickly [OK]

Common Mistakes:

• Ignoring valid pairs in BST
• Assuming no pair without checking all nodes
• Confusing output with null or error

4. Consider this buggy code snippet for FindTarget in a BST:

public bool FindTarget(TreeNode root, int k) {
    HashSet<int> set = new HashSet<int>();
    return DFS(root, k, set);
}

private bool DFS(TreeNode node, int k, HashSet<int> set) {
    if (node == null) return false;
    if (set.Contains(k - node.val)) return true;
    set.Add(node.val);
    DFS(node.left, k, set);
    DFS(node.right, k, set);
    return false;
}

What is the main bug causing incorrect results?

medium

A. The base case should return true instead of false.

B. HashSet is not initialized properly.

C. DFS calls do not return their results, so always returns false.

D. The function should use a queue instead of recursion.

Solution

1. Step 1: Analyze DFS recursive calls

   The DFS calls to left and right subtrees are made but their return values are ignored.

2. Step 2: Understand impact on return value

   Because the recursive calls' results are not returned or checked, the function always returns false unless the first node matches.

3. Step 3: Correct fix

   Return the result of DFS calls combined with OR logic to propagate true upwards.

4. Final Answer:

   DFS calls do not return their results, so always returns false. -> Option C

5. Quick Check:

   Missing return in recursion causes false always [OK]

Hint: Always return recursive call results in DFS [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Incorrect base case return value
• Unnecessary data structure misuse

5. You want to find if there exist two nodes in a BST that sum to a target value. Which approach is the most efficient in terms of time and space? A) Convert BST to sorted list using inorder traversal, then use two pointers to find the sum. B) Use a HashSet during DFS to check complements without extra traversal. C) Check every pair of nodes by traversing the BST twice. D) Insert all node values into a queue and check sums by dequeuing pairs.

hard

A. Use HashSet during DFS to check complements.

B. Convert BST to sorted list and use two pointers.

C. Check every pair by traversing BST twice.

D. Use a queue to check sums by dequeuing pairs.

Solution

1. Step 1: Analyze each approach's efficiency

   Approach A uses O(n) space and O(n) time for traversal plus O(n) for two pointers. Approach B uses O(n) space but only one traversal with O(n) time. Approach C is O(n^2) time, inefficient. Approach D is unclear and inefficient.

2. Step 2: Choose the most efficient method

   Using a HashSet during DFS (Approach B) is efficient in time and space, as it checks complements on the fly without extra traversal.

3. Final Answer:

   Use HashSet during DFS to check complements. -> Option A

4. Quick Check:

   HashSet during DFS = efficient O(n) time and space [OK]

Hint: Use HashSet in one DFS pass for best efficiency [OK]

Common Mistakes:

• Choosing double traversal with two pointers over HashSet
• Trying all pairs causing O(n^2) time
• Using queues unnecessarily increasing complexity