Two Sum in BST in DSA C# - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize empty set

↓

Traverse node

↓

Check if (target - node.val) in set?

↓

Return true

↓

Traverse left subtree

↓

Traverse right subtree

↓

If all nodes visited, return false

We walk through the BST nodes, checking if the complement of the current node's value exists in a set. If yes, we found two numbers summing to target. Otherwise, add current value and continue.

Execution Sample

DSA C#

bool FindTarget(TreeNode root, int k) {
  var set = new HashSet<int>();
  return DFS(root, k, set);
}

bool DFS(TreeNode node, int k, HashSet<int> set) {
  if (node == null) return false;
  if (set.Contains(k - node.val)) return true;
  set.Add(node.val);
  return DFS(node.left, k, set) || DFS(node.right, k, set);
}

This code searches the BST to find if two values sum to k by traversing nodes and checking complements in a set.

Execution Table

Step	Operation	Current Node Value	Set Contents	Action	Visual State
1	Start at root	5	{}	Check if 9 - 5 = 4 in set? No	[5]
2	Add node.val	5	{5}	Add 5 to set	[5]
3	Traverse left	3	{5}	Check if 9 - 3 = 6 in set? No	[3 -> 5]
4	Add node.val	3	{3,5}	Add 3 to set	[3 -> 5]
5	Traverse left	2	{3,5}	Check if 9 - 2 = 7 in set? No	[2 -> 3 -> 5]
6	Add node.val	2	{2,3,5}	Add 2 to set	[2 -> 3 -> 5]
7	Traverse left	null	{2,3,5}	Node null, return false	[2 -> 3 -> 5]
8	Traverse right	null	{2,3,5}	Node null, return false	[2 -> 3 -> 5]
9	Back to 3, traverse right	4	{2,3,5}	Check if 9 - 4 = 5 in set? Yes	[4 -> 3 -> 5]
10	Found pair	4	{2,3,5}	Return true	[4 -> 3 -> 5]

💡 Found two nodes with values 4 and 5 summing to 9, so return true.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	Final
Current Node	5	3	2	Back to 3 then 4	4	Found pair
Set Contents	{}	{5}	{3,5}	{2,3,5}	{2,3,5}	{2,3,5}
Return Value	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we check if (target - node.val) is in the set before adding node.val?

Because we want to find if a previously visited node complements the current node to sum to target. Checking first ensures we don't pair a node with itself. See execution_table step 1 and 9.

What happens when we reach a null node?

We return false immediately because there is no value to check. This is shown in steps 7 and 8 where traversal hits null and returns false.

Why do we use a set to store visited node values?

A set allows quick lookup to check if the complement exists. This makes the search efficient. The set grows as we visit nodes, shown in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the set content?

A {2,3,5}

B {4,3,5}

C {5}

D {}

💡 Hint

Check the 'Set Contents' column at step 9 in execution_table.

At which step does the function find the two nodes that sum to the target?

A Step 4

B Step 6

C Step 9

D Step 7

💡 Hint

Look for the step where 'Check if 9 - 4 = 5 in set? Yes' occurs in execution_table.

If the target was 7 instead of 9, at which step would the function return true?

A Step 6

B Step 5

C It would not return true in these steps

D Step 9

💡 Hint

Check the complements calculated in execution_table and see if any pair sums to 7.

Concept Snapshot

Two Sum in BST:
- Traverse BST nodes using DFS
- Keep a set of visited node values
- For each node, check if (target - node.val) is in set
- If yes, return true; else add node.val to set
- Return false if no pair found after full traversal

Full Transcript

This visualization shows how to find two numbers in a binary search tree that add up to a target sum. We start at the root and keep a set of visited values. For each node, we check if the complement (target minus current node's value) is already in the set. If yes, we found the pair and return true. Otherwise, we add the current node's value to the set and continue traversing left and right subtrees. If we reach a null node, we return false. The execution table traces each step, showing the current node, set contents, and actions. The variable tracker shows how the current node and set change over time. Key moments clarify why we check the set before adding and what happens at null nodes. The quiz tests understanding of set contents and when the pair is found. This method efficiently finds two sum in BST using DFS and a hash set.

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Find two nodes in the BST whose values add up to a target sum.

B. Find the maximum value in the BST.

C. Count the total number of nodes in the BST.

D. Check if the BST is balanced.

Solution

1. Step 1: Understand the problem statement

   The problem asks to find two nodes in a Binary Search Tree (BST) such that their values add up to a given target sum.

2. Step 2: Identify the goal

   The goal is to check if such a pair exists, not to find max, count nodes, or check balance.

3. Final Answer:

   Find two nodes in the BST whose values add up to a target sum. -> Option A

4. Quick Check:

   Two Sum in BST = Find pair with target sum [OK]

Hint: Look for two values adding to target in BST nodes [OK]

Common Mistakes:

• Confusing with finding max or min value
• Thinking it counts nodes instead of finding pairs
• Assuming it checks tree balance

2. Which of the following C# method signatures is correct for a function that checks if two nodes in a BST sum to a target value?

easy

A. string FindTarget(TreeNode root, int target)

B. bool FindTarget(TreeNode root, int target)

C. void FindTarget(TreeNode root, int target)

D. int FindTarget(TreeNode root, int target)

Solution

1. Step 1: Understand the expected return type

   The function should return true or false depending on whether two nodes sum to the target, so return type must be bool.

2. Step 2: Check method signature options

   bool FindTarget(TreeNode root, int target) returns bool, matching the requirement. Others return int, void, or string, which are incorrect for this purpose.

3. Final Answer:

   bool FindTarget(TreeNode root, int target) -> Option B

4. Quick Check:

   Return type bool for true/false check [OK]

Hint: Function returns true/false, so use bool return type [OK]

Common Mistakes:

• Using void return type and expecting a result
• Returning int or string instead of bool
• Incorrect parameter types

3. Given the BST below and target = 9, what will the function FindTarget return?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. runtime error

B. false

C. null

D. true

Solution

1. Step 1: Identify pairs that sum to target 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All these pairs exist in the BST.

2. Step 2: Confirm function behavior

   Since at least one pair (e.g., 2 and 7) sums to 9, the function should return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Pair exists with sum 9 = true [OK]

Hint: Check all node pairs for target sum quickly [OK]

Common Mistakes:

• Ignoring valid pairs in BST
• Assuming no pair without checking all nodes
• Confusing output with null or error

4. Consider this buggy code snippet for FindTarget in a BST:

public bool FindTarget(TreeNode root, int k) {
    HashSet<int> set = new HashSet<int>();
    return DFS(root, k, set);
}

private bool DFS(TreeNode node, int k, HashSet<int> set) {
    if (node == null) return false;
    if (set.Contains(k - node.val)) return true;
    set.Add(node.val);
    DFS(node.left, k, set);
    DFS(node.right, k, set);
    return false;
}

What is the main bug causing incorrect results?

medium

A. The base case should return true instead of false.

B. HashSet is not initialized properly.

C. DFS calls do not return their results, so always returns false.

D. The function should use a queue instead of recursion.

Solution

1. Step 1: Analyze DFS recursive calls

   The DFS calls to left and right subtrees are made but their return values are ignored.

2. Step 2: Understand impact on return value

   Because the recursive calls' results are not returned or checked, the function always returns false unless the first node matches.

3. Step 3: Correct fix

   Return the result of DFS calls combined with OR logic to propagate true upwards.

4. Final Answer:

   DFS calls do not return their results, so always returns false. -> Option C

5. Quick Check:

   Missing return in recursion causes false always [OK]

Hint: Always return recursive call results in DFS [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Incorrect base case return value
• Unnecessary data structure misuse

5. You want to find if there exist two nodes in a BST that sum to a target value. Which approach is the most efficient in terms of time and space? A) Convert BST to sorted list using inorder traversal, then use two pointers to find the sum. B) Use a HashSet during DFS to check complements without extra traversal. C) Check every pair of nodes by traversing the BST twice. D) Insert all node values into a queue and check sums by dequeuing pairs.

hard

A. Use HashSet during DFS to check complements.

B. Convert BST to sorted list and use two pointers.

C. Check every pair by traversing BST twice.

D. Use a queue to check sums by dequeuing pairs.

Solution

1. Step 1: Analyze each approach's efficiency

   Approach A uses O(n) space and O(n) time for traversal plus O(n) for two pointers. Approach B uses O(n) space but only one traversal with O(n) time. Approach C is O(n^2) time, inefficient. Approach D is unclear and inefficient.

2. Step 2: Choose the most efficient method

   Using a HashSet during DFS (Approach B) is efficient in time and space, as it checks complements on the fly without extra traversal.

3. Final Answer:

   Use HashSet during DFS to check complements. -> Option A

4. Quick Check:

   HashSet during DFS = efficient O(n) time and space [OK]

Hint: Use HashSet in one DFS pass for best efficiency [OK]

Common Mistakes:

• Choosing double traversal with two pointers over HashSet
• Trying all pairs causing O(n^2) time
• Using queues unnecessarily increasing complexity