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.

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, moving inward to find the perfect pair.

      5
     / \
    3   7
   / \   \
  2   4   8

Two pointers start: one at smallest (2), one at largest (8).

Dry Run Walkthrough

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

Goal: Find two nodes whose values add up to 9

Step 1: Initialize left pointer at smallest node (2) and right pointer at largest node (8)

Left -> 2, Right -> 8

Why: We start with the smallest and largest values to check sums efficiently

Step 2: Calculate sum: 2 + 8 = 10, which is greater than target 9

Left -> 2, Right -> 8

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

Step 3: Move right pointer to next smaller node (7)

Left -> 2, Right -> 7

Why: Try smaller value to reduce sum

Step 4: Calculate sum: 2 + 7 = 9, equals target

Left -> 2, Right -> 7

Why: Found the pair that sums to target

Result:

2 -> ... -> 7
Pair found: 2 + 7 = 9

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// BST node structure
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// Stack for inorder traversal
typedef struct Stack {
    Node** arr;
    int top;
    int capacity;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->arr = (Node**)malloc(sizeof(Node*) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, Node* node) {
    if (stack->top < stack->capacity - 1) {
        stack->arr[++stack->top] = node;
    }
}

Node* pop(Stack* stack) {
    if (!isEmpty(stack)) {
        return stack->arr[stack->top--];
    }
    return NULL;
}

// Create new BST node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert value into BST
Node* insert(Node* root, int val) {
    if (root == NULL) return newNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

// Iterator for inorder traversal (ascending)
typedef struct {
    Stack* stack;
    Node* curr;
} BSTIterator;

BSTIterator* createIterator(Node* root, bool forward, int capacity) {
    BSTIterator* it = (BSTIterator*)malloc(sizeof(BSTIterator));
    it->stack = createStack(capacity);
    it->curr = root;
    return it;
}

// Move iterator forward (inorder)
int next(BSTIterator* it) {
    while (it->curr != NULL) {
        push(it->stack, it->curr);
        it->curr = it->curr->left;
    }
    Node* node = pop(it->stack);
    int val = node->val;
    it->curr = node->right;
    return val;
}

// Iterator for reverse inorder traversal (descending)
typedef struct {
    Stack* stack;
    Node* curr;
} BSTRevIterator;

BSTRevIterator* createRevIterator(Node* root, int capacity) {
    BSTRevIterator* it = (BSTRevIterator*)malloc(sizeof(BSTRevIterator));
    it->stack = createStack(capacity);
    it->curr = root;
    return it;
}

int prev(BSTRevIterator* it) {
    while (it->curr != NULL) {
        push(it->stack, it->curr);
        it->curr = it->curr->right;
    }
    Node* node = pop(it->stack);
    int val = node->val;
    it->curr = node->left;
    return val;
}

// Count nodes in BST for stack capacity
int countNodes(Node* root) {
    if (!root) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Two Sum in BST function
bool twoSumBST(Node* root, int target) {
    if (!root) return false;
    int n = countNodes(root);
    BSTIterator* leftIt = createIterator(root, true, n);
    BSTRevIterator* rightIt = createRevIterator(root, n);

    int leftVal = next(leftIt);
    int rightVal = prev(rightIt);

    while (leftVal < rightVal) {
        int sum = leftVal + rightVal;
        if (sum == target) {
            printf("Pair found: %d + %d = %d\n", leftVal, rightVal, target);
            return true;
        } else if (sum < target) {
            leftVal = next(leftIt); // move left pointer forward
        } else {
            rightVal = prev(rightIt); // move right pointer backward
        }
    }
    printf("No pair found that sums to %d\n", target);
    return false;
}

// Print BST inorder (for visualization)
void printInorder(Node* root) {
    if (!root) return;
    printInorder(root->left);
    printf("%d -> ", root->val);
    printInorder(root->right);
}

int main() {
    Node* root = NULL;
    int values[] = {5, 3, 7, 2, 4, 8};
    int n = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }
    printf("BST inorder: ");
    printInorder(root);
    printf("null\n");

    int target = 9;
    twoSumBST(root, target);
    return 0;
}

int leftVal = next(leftIt); int rightVal = prev(rightIt);

Initialize left and right pointers at smallest and largest nodes

while (leftVal < rightVal) {

Loop until pointers cross, ensuring unique pairs

int sum = leftVal + rightVal;

Calculate sum of current pair

if (sum == target) {

Check if sum matches target

leftVal = next(leftIt);

Move left pointer forward to increase sum

rightVal = prev(rightIt);

Move right pointer backward to decrease sum

Output

BST inorder: 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> null

Pair found: 2 + 7 = 9

Complexity Analysis

Time: O(n) because each node is visited at most once by the two iterators

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

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

Edge Cases

Empty BST

Returns false immediately, no pairs to check

DSA C

if (!root) return false;

Single node BST

No pair possible, returns false

DSA C

while (leftVal < rightVal) {

No pair sums to target

Iterators cross without finding pair, prints no pair found

DSA C

printf("No pair found that sums to %d\n", target);

When to Use This Pattern

When asked to find two values summing to a target in a BST, use two-pointer traversal with inorder and reverse inorder iterators to efficiently find the pair.

Common Mistakes

Mistake: Using a normal inorder traversal and checking all pairs leading to O(n^2) time
Fix: Use two iterators from smallest and largest nodes moving inward to achieve O(n) time

Summary

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

Use when you need to find pairs summing to a value efficiently in a BST.

The key is using two pointers moving inward from smallest and largest values using BST iterators.

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