Two Sum in BST in DSA C++ - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Inorder traversal to get sorted array

↓

Initialize two pointers: left=0, right=end

↓

Check sum = arr[left

↓

Return True

↓

Repeat until left >= right

↓

Return False if no pair found

First, we get all BST values in sorted order using inorder traversal. Then, we use two pointers from start and end to find if any two numbers sum to the target.

Execution Sample

DSA C++

void inorder(TreeNode* root, vector<int>& nums) {
  if (!root) return;
  inorder(root->left, nums);
  nums.push_back(root->val);
  inorder(root->right, nums);
}

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 / Array State	Pointers (left, right)	Sum Checked	Action	Visual State
1	Inorder traversal start	Visited: [] / Array: []	-	-	Traverse left subtree	BST nodes visited: 4,2,5,1,3; Array after traversal: [1,2,3,4,5]
2	Inorder traversal complete	Visited all nodes / Array: [1,2,3,4,5]	-	-	Prepare two pointers	Array ready: [1,2,3,4,5]
3	Initialize pointers	[1,2,3,4,5]	left=0, right=4	-	Calculate sum	Pointers at values 1 and 5
4	Check sum	[1,2,3,4,5]	left=0, right=4	1+5=6	6 < 7, move left++	left moves to index 1 (value 2)
5	Check sum	[1,2,3,4,5]	left=1, right=4	2+5=7	7 == 7, pair found	Return True
6	End	[1,2,3,4,5]	-	-	Stop search	Result: True

💡 Sum found at step 5 with values 2 and 5 equal to target 7

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
nums	[]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]
left	-	0	1	1	-
right	-	4	4	4	-
sum	-	-	6	7	-

Key Moments - 3 Insights

Why do we do an inorder traversal first?

Inorder traversal visits BST nodes in sorted order, which lets us use two pointers efficiently to find the sum. See execution_table step 1 and 2 where array is built.

Why move left pointer when sum is less than target?

Because the array is sorted, increasing left pointer moves to a bigger number, increasing sum. See execution_table step 4 where sum=6 < 7, so left moves from 0 to 1.

Why stop when left >= right?

Because left and right pointers crossing means all pairs checked. No pair found means return false. See concept_flow and execution_table step 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum checked at step 4?

A 7

B 6

C 5

D 8

💡 Hint

Check the 'Sum Checked' column at step 4 in execution_table

At which step does the algorithm find the pair that sums to the target?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Action' column for when sum == target in execution_table

If the target was 10 instead of 7, what would happen to the pointers after step 4?

A Left pointer moves right

B Right pointer moves left

C Both pointers stay the same

D Algorithm stops immediately

💡 Hint

Recall that if sum < target, left pointer moves right as per execution_table step 4

Concept Snapshot

Two Sum in BST:
- Use inorder traversal to get sorted array of BST values
- Use two pointers (left at start, right at end)
- Check sum = arr[left] + arr[right]
- If sum == target, return true
- If sum < target, move left pointer right
- If sum > target, move right pointer left
- Stop when pointers cross, return false

Full Transcript

To find if two numbers in a BST sum to a target, first do an inorder traversal 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 the sum equals the target, return true. If the sum is less than the target, move the left pointer right to increase sum. If the sum is greater, move the right pointer left to decrease sum. Repeat until pointers cross. If no pair found, return false.