Two Sum in BST in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum Check in BST

What is the output of the following code that checks if there exist two nodes in the BST whose values sum to 9?

DSA C

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

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

bool findTargetHelper(Node* root, int k, int* arr, int* size) {
    if (!root) return false;
    if (findTargetHelper(root->left, k, arr, size)) return true;
    for (int i = 0; i < *size; i++) {
        if (arr[i] == k - root->val) return true;
    }
    arr[(*size)++] = root->val;
    return findTargetHelper(root->right, k, arr, size);
}

bool findTarget(Node* root, int k) {
    int arr[1000];
    int size = 0;
    return findTargetHelper(root, k, arr, &size);
}

int main() {
    Node n1 = {5, NULL, NULL};
    Node n2 = {3, NULL, NULL};
    Node n3 = {6, NULL, NULL};
    Node n4 = {2, NULL, NULL};
    Node n5 = {4, NULL, NULL};
    Node n6 = {7, NULL, NULL};

    n1.left = &n2; n1.right = &n3;
    n2.left = &n4; n2.right = &n5;
    n3.right = &n6;

    if (findTarget(&n1, 9)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

A Compilation error

B true

C false

D Runtime error

💡 Hint

Think about pairs of nodes that add up to 9 in the BST.

The BST contains nodes with values 2,3,4,5,6,7. The pair (2,7) sums to 9, so the function returns true.

🧠 Conceptual

intermediate

Number of Unique Pairs Summing to Target in BST

Given a BST with unique values, how many unique pairs of nodes sum to 10 in this BST? BST nodes: 1, 3, 4, 5, 7, 9

A 4

B 3

C 1

D 2

💡 Hint

Check pairs that add up to 10 without repeating nodes.

Pairs are (1,9), (3,7), and (4,6) but 6 is not in BST, so only (1,9) and (3,7) count. Also (5,5) is invalid since nodes are unique. So total 2 pairs.

❓ Predict Output

advanced

Output of Two Sum Using Inorder and Two Pointers

What is the output of the following code that uses inorder traversal and two pointers to find if two nodes sum to 11?

DSA C

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

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

void inorder(Node* root, int* arr, int* size) {
    if (!root) return;
    inorder(root->left, arr, size);
    arr[(*size)++] = root->val;
    inorder(root->right, arr, size);
}

bool findTarget(Node* root, int k) {
    int arr[1000];
    int size = 0;
    inorder(root, arr, &size);
    int left = 0, right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == k) return true;
        else if (sum < k) left++;
        else right--;
    }
    return false;
}

int main() {
    Node n1 = {8, NULL, NULL};
    Node n2 = {3, NULL, NULL};
    Node n3 = {10, NULL, NULL};
    Node n4 = {1, NULL, NULL};
    Node n5 = {6, NULL, NULL};
    Node n6 = {14, NULL, NULL};
    Node n7 = {4, NULL, NULL};
    Node n8 = {7, NULL, NULL};

    n1.left = &n2; n1.right = &n3;
    n2.left = &n4; n2.right = &n5;
    n3.right = &n6;
    n5.left = &n7; n5.right = &n8;

    if (findTarget(&n1, 11)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Use the sorted array from inorder traversal to find pairs.

Inorder traversal gives sorted array [1,3,4,6,7,8,10,14]. The pair (4,7) sums to 11, so output is true.

🔧 Debug

advanced

Identify the Bug in Two Sum BST Code

What error will this code produce when checking if two nodes sum to 9 in the BST?

DSA C

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

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

bool findTarget(Node* root, int k) {
    if (!root) return false;
    bool left = findTarget(root->left, k);
    bool right = findTarget(root->right, k);
    if (left || right) return true;
    if (root->val == k - root->val) return true;
    return false;
}

int main() {
    Node n1 = {5, NULL, NULL};
    Node n2 = {3, NULL, NULL};
    Node n3 = {6, NULL, NULL};
    Node n4 = {2, NULL, NULL};
    Node n5 = {4, NULL, NULL};
    Node n6 = {7, NULL, NULL};

    n1.left = &n2; n1.right = &n3;
    n2.left = &n4; n2.right = &n5;
    n3.right = &n6;

    if (findTarget(&n1, 9)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

A Always returns false

B Stack overflow due to infinite recursion

C Returns true only if root value is half of k

D Compilation error due to variable shadowing

💡 Hint

Check how the code checks pairs and if it stores visited nodes.

The code only checks if root->val equals k - root->val, which is only true if k is twice root->val. It does not check pairs of different nodes, so it always returns false for pairs.

🚀 Application

expert

Minimum Space Two Sum in BST

Which approach uses the least extra space to check if two nodes in a BST sum to a target value k?

A Inorder traversal storing all nodes in an array, then two pointers

B Hash set storing visited node values during DFS

C Using two iterators: one for smallest and one for largest node, moving inward

D Brute force checking all pairs by traversing BST multiple times

💡 Hint

Think about how to avoid storing all nodes or many values.

Using two iterators (one from smallest, one from largest) simulates two pointers without storing all nodes, using O(h) space where h is tree height, less than storing all nodes.

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