Two Sum in BST in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the structure for a binary search tree node.

DSA C

typedef struct TreeNode {
    int val;
    struct TreeNode *[1];
    struct TreeNode *right;
} TreeNode;

Drag options to blanks, or click blank then click option'

Aparent

Bleft

Cchild

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' instead of 'left' pointer.

The left pointer is used to point to the left child in a BST node.

2fill in blank

medium

Complete the code to perform in-order traversal of the BST.

DSA C

void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->[1]);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

Drag options to blanks, or click blank then click option'

Aleft

Bparent

Cnext

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' for first recursive call.

In-order traversal visits the left subtree first, so we use root->left.

3fill in blank

hard

Fix the error in the function that searches for a value in the BST.

DSA C

int searchBST(TreeNode* root, int target) {
    if (root == NULL) return 0;
    if (root->val == target) return 1;
    if (target < root->val) return searchBST(root->[1], target);
    else return searchBST(root->right, target);
}

Drag options to blanks, or click blank then click option'

Anext

Bright

Cparent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using root->right instead of root->left for smaller values.

When target is less than root value, search left subtree using root->left.

4fill in blank

hard

Fill both blanks to complete the function that checks if there exist two elements in BST that sum to target.

DSA C

int findTarget(TreeNode* root, TreeNode* curr, int k) {
    if (curr == NULL) return 0;
    int complement = k - curr->val;
    if (complement != curr->val && searchBST(root, [1])) return 1;
    return findTarget(root, curr->[2], k) || findTarget(root, curr->right, k);
}

Drag options to blanks, or click blank then click option'

Acomplement

Bcurr->val

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using curr->val instead of complement in search.

Using curr->right instead of curr->left for next traversal.

The complement value is searched in the BST, and the traversal moves to the left child next.

5fill in blank

hard

Fill all three blanks to complete the main function that initiates the two sum check in BST.

DSA C

int findTargetInBST(TreeNode* root, int k) {
    if (root == NULL) return 0;
    return findTarget(root, [1], [2]);
}

// Usage example:
// int result = findTargetInBST(root, [3]);

Drag options to blanks, or click blank then click option'

Aroot

Bk

C0

Droot->val

Attempts:

3 left

💡 Hint

Common Mistakes

Passing root->val instead of root as current node.

Passing 0 instead of k as target.

The function starts with the root node and target k, and the example call uses k as the target sum.

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