Two Sum in BST in DSA Java - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize empty set

↓

Inorder traversal node

↓

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

Yes→Return True

No↓

Add node.val to set

↓

Traverse left and right subtrees

↓

If all nodes checked, return False

Traverse BST in order, check if complement exists in set, return true if found, else add value and continue.

Execution Sample

DSA Java

boolean findTarget(TreeNode root, int k) {
  Set<Integer> set = new HashSet<>();
  return inorder(root, k, set);
}

boolean inorder(TreeNode node, int k, Set<Integer> set) {
  if (node == null) return false;
  if (inorder(node.left, k, set)) return true;
  if (set.contains(k - node.val)) return true;
  set.add(node.val);
  return inorder(node.right, k, set);
}

Checks if two numbers in BST sum to target k using inorder traversal and a set.

Execution Table

Step	Operation	Current Node	Set Contents	Check Complement (k - node.val)	Result	Visual State
1	Visit node	4	{}	6 (10 - 4)	No	4
2	Add node.val	4	{4}	-	-	4
3	Visit node	2	{4}	8 (10 - 2)	No	4 -> 2
4	Add node.val	2	{4, 2}	-	-	4 -> 2
5	Visit node	1	{4, 2}	9 (10 - 1)	No	4 -> 2 -> 1
6	Add node.val	1	{4, 2, 1}	-	-	4 -> 2 -> 1
7	Back to node	2	{4, 2, 1}	-	-	4 -> 2 -> 1
8	Back to node	4	{4, 2, 1}	-	-	4 -> 2 -> 1
9	Visit node	6	{4, 2, 1}	4 (10 - 6)	Yes	4 -> 2 -> 1 -> 6
10	Return True	6	{4, 2, 1}	4 (found)	True	4 -> 2 -> 1 -> 6

💡 At step 9, complement 4 found in set, so return True.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	Final
set	{}	{4}	{4, 2}	{4, 2, 1}	{4, 2, 1}	{4, 2, 1}
current node	4	2	1	1	6	6
result	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 before adding avoids using the same node twice. See step 9 in execution_table where complement 4 is found in set.

Why do we use inorder traversal for this problem?

Inorder traversal visits nodes in ascending order, but here it mainly ensures all nodes are visited systematically. The set handles complement checks. See steps 1-9 showing traversal order.

What happens if the BST is empty?

The traversal immediately returns false because node is null at start (step 1). No nodes to check means no pairs.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the content of the set?

A {}

B {4}

C {4, 2}

D {4, 2, 1}

💡 Hint

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

At which step does the function find the two sum and return true?

A Step 6

B Step 9

C Step 10

D Step 4

💡 Hint

Look at the 'Result' column and 'Check Complement' at step 9 in execution_table.

If the target was 7 instead of 10, at which step would the complement be found?

A Step 3

B Step 5

C Step 9

D No complement found

💡 Hint

For target=7, recalculate the complements (7 - node.val) using the 'Current Node' at each step and check if they exist in the 'Set Contents' at that step.

Concept Snapshot

Two Sum in BST:
- Traverse BST inorder
- Use a set to store visited values
- For each node, check if (target - node.val) in set
- If yes, return true
- Else add node.val and continue
- Return false if no pair found

Full Transcript

This visualization shows how to find if two numbers in a Binary Search Tree sum to a target value. We do an inorder traversal visiting nodes in ascending order. At each node, we check if the complement (target minus current node's value) exists in a set of previously visited values. If found, we return true immediately. Otherwise, we add the current node's value to the set and continue. The execution table tracks each step, showing the current node, set contents, complement check, and the visual state of the BST traversal. Key moments clarify why we check complements before adding values and why inorder traversal is used. The quiz tests understanding of set contents and when the function returns true.

Practice

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

easy

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

B. Find the maximum value in the BST.

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

D. Check if the BST is balanced.

Solution

1. Step 1: Understand the problem statement

   The problem asks to find if there exist two nodes in the BST such that their values add up to a given target.

2. Step 2: Identify the goal

   The goal is to check for the existence of such a pair, not to find max, balance, or count nodes.

3. Final Answer:

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

4. Quick Check:

   Two Sum in BST means finding two nodes summing to target [OK]

Hint: Remember Two Sum means pair sums to target [OK]

Common Mistakes:

• Confusing Two Sum with finding max value
• Thinking problem is about BST balance
• Counting nodes instead of finding pairs

2. Which of the following Java method signatures correctly represents a function to solve Two Sum in BST?

easy

A. public int findSum(TreeNode root, int k)

B. public boolean findTarget(TreeNode root, int k)

C. public void findTarget(TreeNode root, int k)

D. public TreeNode findPair(TreeNode root, int k)

Solution

1. Step 1: Understand the return type needed

   The function should return true or false if a pair exists, so return type is boolean.

2. Step 2: Check method signatures

   public boolean findTarget(TreeNode root, int k) returns boolean and accepts root and target, matching the problem requirements.

3. Final Answer:

   public boolean findTarget(TreeNode root, int k) -> Option B

4. Quick Check:

   Boolean return for existence check [OK]

Hint: Two Sum returns true/false, so use boolean return [OK]

Common Mistakes:

• Using void return type instead of boolean
• Returning int instead of boolean
• Returning TreeNode instead of boolean

3. Given the BST below and target = 9, what will the output of findTarget(root, 9) be?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. true

B. false

C. null

D. Runtime Error

Solution

1. Step 1: Identify pairs that sum to 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All valid pairs exist.

2. Step 2: Confirm function returns true if any pair found

   Since pairs exist, function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pairs 2+7 or 3+6 sum to 9 [OK]

Hint: Check pairs adding to target in BST nodes [OK]

Common Mistakes:

• Ignoring valid pairs and returning false
• Confusing output with node values
• Assuming null or error without reason

4. Consider this buggy code snippet for Two Sum in BST:

public boolean findTarget(TreeNode root, int k) {
    Set<Integer> set = new HashSet<>();
    return dfs(root, k, set);
}

private boolean dfs(TreeNode node, int k, Set<Integer> 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. Using HashSet instead of ArrayList.

B. Adding node values after checking set.

C. Not checking if root is null in findTarget.

D. Missing return statements from recursive calls in dfs.

Solution

1. Step 1: Analyze dfs recursive calls

   dfs calls itself on left and right but ignores their return values.

2. Step 2: Understand impact of missing returns

   Without returning results of recursive calls, function always returns false unless first node matches.

3. Step 3: Correct fix

   Return true if either left or right dfs call returns true.

4. Final Answer:

   Missing return statements from recursive calls in dfs. -> Option D

5. Quick Check:

   Return recursive calls to propagate true [OK]

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

Common Mistakes:

• Ignoring return values of recursive calls
• Using wrong data structure for lookup
• Not handling null root properly

5. You want to optimize Two Sum in BST to use O(h) space, where h is tree height. Which approach is best?

hard

A. Use two iterators: one in-order and one reverse in-order traversal.

B. Store all node values in a list and use two pointers.

C. Use a HashSet to store visited nodes during DFS.

D. Convert BST to sorted array and binary search for complements.

Solution

1. Step 1: Understand space complexity of approaches

   Storing all nodes uses O(n) space; HashSet also O(n); array conversion O(n).

2. Step 2: Two iterator approach

   Using two iterators (in-order and reverse in-order) simulates two pointers with O(h) space.

3. Step 3: Choose best approach

   Use two iterators: one in-order and one reverse in-order traversal. uses O(h) space and is optimal for BST Two Sum.

4. Final Answer:

   Use two iterators: one in-order and one reverse in-order traversal. -> Option A

5. Quick Check:

   Two iterators give O(h) space [OK]

Hint: Two pointers in BST use two iterators for O(h) space [OK]

Common Mistakes:

• Using full list storage causing O(n) space
• Relying on HashSet which uses O(n) space
• Ignoring BST properties for optimization