Two Sum in BST in DSA C - Execution Trace

Concept Flow - Two Sum in BST

Start at root node

↓

Traverse BST Inorder

↓

Collect values in sorted list

↓

Initialize two pointers: left=0, right=end

↓

Check sum = list[left

↓

left++

↓

Repeat until left >= right or found

Traverse the BST in order to get sorted values, then use two pointers to find if two values sum to target.

Execution Sample

DSA C

bool findTarget(TreeNode* root, int k) {
  vector<int> nums;
  inorder(root, nums);
  int left = 0, right = nums.size() - 1;
  while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == k) return true;
    else if (sum < k) left++;
    else right--;
  }
  return false;
}

This code finds if two numbers in BST sum to k by inorder traversal and two-pointer search.

Execution Table

Step	Operation	Nodes Visited	Pointer Changes	Visual State
1	Inorder traversal start	Root (5)	nums = []	[]
2	Visit left child of 3 (2)	2	nums = [2]	[2]
3	Visit node (3)	3	nums = [2,3]	[2,3]
4	Visit right child of 3 (4)	4	nums = [2,3,4]	[2,3,4]
5	Visit root (5)	5	nums = [2,3,4,5]	[2,3,4,5]
6	Visit right child (6)	6	nums = [2,3,4,5,6]	[2,3,4,5,6]
7	Initialize pointers	N/A	left=0, right=4	[2,3,4,5,6]
8	Check sum nums[left]+nums[right]=2+6=8	N/A	sum=8	[2,3,4,5,6]
9	sum < k(9), move left pointer	N/A	left=1, right=4	[2,3,4,5,6]
10	Check sum nums[left]+nums[right]=3+6=9	N/A	sum=9	[2,3,4,5,6]
11	sum == k(9), found pair	N/A	Return true	[2,3,4,5,6]

💡 Found two nodes with sum equal to target k=9 at step 11.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 9	After Step 11
nums	[]	[2]	[2,3,4]	[2,3,4,5,6]	[2,3,4,5,6]	[2,3,4,5,6]	[2,3,4,5,6]
left	N/A	N/A	N/A	N/A	0	1	1
right	N/A	N/A	N/A	N/A	4	4	4
sum	N/A	N/A	N/A	N/A	N/A	8	9

Key Moments - 3 Insights

Why do we do an inorder traversal first instead of checking pairs directly in the BST?

Inorder traversal gives a sorted list of values, which allows using two pointers efficiently to find the sum. Direct pair checking in BST would be complex and less efficient. See steps 1-6 in execution_table.

Why do we move the left pointer when sum < target and right pointer when sum > target?

Because the list is sorted, increasing left pointer moves to a bigger number to increase sum, decreasing right pointer moves to a smaller number to decrease sum. See steps 8-10 in execution_table.

What happens if the BST has duplicate values?

Duplicates appear in the sorted list and can form pairs if their sum equals target. The two-pointer method still works correctly. The traversal collects all nodes including duplicates as shown in variable 'nums'.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the value of 'left' pointer?

A 0

B 1

C 4

D 2

💡 Hint

Check the 'Pointer Changes' column at step 9 in execution_table.

At which step does the sum of nums[left] + nums[right] equal the target k=9?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for 'sum == k' in the 'Operation' column in execution_table.

If the target k was 7 instead of 9, what would happen to the pointers after step 8?

A Left pointer would move forward

B Right pointer would move backward

C Both pointers would move

D No pointer moves

💡 Hint

Compare sum at step 8 (8) with new target 7 and see pointer movement rules in execution_table.

Concept Snapshot

Two Sum in BST:
- Traverse BST inorder to get sorted list
- Use two pointers (left, right) on list
- If sum < target, move left forward
- If sum > target, move right backward
- If sum == target, return true
- Stop when pointers cross

Full Transcript

To find if two numbers in a BST sum to a target, first traverse the BST inorder to get a sorted list of values. Then use two pointers at the start and end of this list. Check the sum of values at these pointers. If sum equals target, return true. If sum is less, move left pointer forward to increase sum. If sum is more, move right pointer backward to decrease sum. Repeat until pointers meet or pair found.

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