Two Sum in BST in DSA C - Build from Scratch

Two Sum in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. Your task is to find if there are two numbers in this tree that add up to a specific target number.Imagine you have a collection of numbered boxes arranged in a special order (BST). You want to check if you can pick two boxes whose numbers add up to a given number.

🎯 Goal: Build a program in C that creates a BST with given numbers, sets a target sum, and checks if any two numbers in the BST add up to that target.

📋 What You'll Learn

Create a BST with the exact numbers: 5, 3, 7, 2, 4, 6, 8

Create an integer variable called target and set it to 9

Write a function findTarget that returns 1 if two numbers in the BST add up to target, else 0

Print the result (1 or 0) using printf

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that sum to a target is common in finance, inventory management, and data analysis. Using a BST helps keep data sorted and efficient to search.

💼 Career

Understanding BSTs and two sum problems is important for software engineering roles that involve data structures, algorithms, and problem solving.

1

Create the BST with given numbers

Create a BST by defining a struct TreeNode and build the tree with these exact numbers inserted in this order: 5, 3, 7, 2, 4, 6, 8. Use a function insertNode to insert nodes. Define a pointer root and insert the numbers to build the BST.

DSA C

// Define struct TreeNode and insertNode function
// Create TreeNode* root and insert 5, 3, 7, 2, 4, 6, 8
// Your code here

Hint

Define a struct TreeNode with val, left, and right. Write insertNode to add values in BST order. Insert the numbers one by one into root.

2

Set the target sum

Create an integer variable called target and set it to 9.

DSA C

#include 
#include 

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

struct TreeNode* insertNode(struct TreeNode* root, int val) {
    if (root == NULL) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

int main() {
    struct TreeNode* root = NULL;
    root = insertNode(root, 5);
    root = insertNode(root, 3);
    root = insertNode(root, 7);
    root = insertNode(root, 2);
    root = insertNode(root, 4);
    root = insertNode(root, 6);
    root = insertNode(root, 8);

    int target = 9;  // Your code here

    return 0;
}

Hint

Just add int target = 9; inside main after building the BST.

3

Write the function to find two numbers that sum to target

Write a function int findTarget(struct TreeNode* root, int target) that returns 1 if there exist two numbers in the BST that add up to target, otherwise returns 0. Use an in-order traversal to collect values in an array, then use two pointers to find the sum.

DSA C

#include 
#include 

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

struct TreeNode* insertNode(struct TreeNode* root, int val) {
    if (root == NULL) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

// Write findTarget function here

int main() {
    struct TreeNode* root = NULL;
    root = insertNode(root, 5);
    root = insertNode(root, 3);
    root = insertNode(root, 7);
    root = insertNode(root, 2);
    root = insertNode(root, 4);
    root = insertNode(root, 6);
    root = insertNode(root, 8);

    int target = 9;

    // Your code here

    return 0;
}

Hint

Use an inorderTraversal function to collect BST values in sorted order into an array. Then use two pointers, left and right, to check if any two numbers add up to target.

4

Print the result

Print the result of findTarget(root, target) using printf. It should print 1 if two numbers add up to target, otherwise 0.

DSA C

#include 
#include 

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

struct TreeNode* insertNode(struct TreeNode* root, int val) {
    if (root == NULL) {
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

void inorderTraversal(struct TreeNode* root, int* arr, int* size) {
    if (root == NULL) return;
    inorderTraversal(root->left, arr, size);
    arr[*size] = root->val;
    (*size)++;
    inorderTraversal(root->right, arr, size);
}

int findTarget(struct TreeNode* root, int target) {
    int arr[100];
    int size = 0;
    inorderTraversal(root, arr, &size);
    int left = 0, right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return 1;
        else if (sum < target) left++;
        else right--;
    }
    return 0;
}

int main() {
    struct TreeNode* root = NULL;
    root = insertNode(root, 5);
    root = insertNode(root, 3);
    root = insertNode(root, 7);
    root = insertNode(root, 2);
    root = insertNode(root, 4);
    root = insertNode(root, 6);
    root = insertNode(root, 8);

    int target = 9;

    int result = findTarget(root, target);

    printf("%d\n", result);  // Your code here

    return 0;
}

Hint

Use printf("%d\n", result); to print the result returned by findTarget.

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