Two Sum in BST in DSA Python - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize two pointers: left, right

↓

While left < right

↓

Calculate sum = left.val + right.val

↓

If sum == target

→Return True

↓

If sum < target

→Move left to next larger node

↓

If sum > target

→Move right to next smaller node

↓

Repeat until left meets right

↓

Return False if no pair found

We use two pointers moving inward on BST's sorted order to find two nodes summing to target.

Execution Sample

DSA Python

def find_target(root, k):
    left, right = BSTIterator(root, forward=True), BSTIterator(root, forward=False)
    l, r = left.next(), right.next()
    while l < r:
        s = l + r
        if s == k:
            return True
        elif s < k:
            l = left.next()
        else:
            r = right.next()
    return False

This code uses two BST iterators to find if two nodes sum to k.

Execution Table

Step	Operation	Left Pointer Node	Right Pointer Node	Sum	Action	Visual State
1	Initialize left and right iterators	Node 2	Node 9	2 + 9 = 11	11 < 12, move left pointer forward	2 -> 3 -> 5 -> 7 -> 9
2	Move left pointer forward	Node 3	Node 9	3 + 9 = 12	Sum equals target, return True	2 -> 3 -> 5 -> 7 -> 9
Exit	Found pair (3,9) with sum 12	Node 3	Node 9	12	Return True	2 -> 3 -> 5 -> 7 -> 9

💡 Sum equals target at step 2, so function returns True.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
left pointer (l)	Node 2	Node 2	Node 3	Node 3
right pointer (r)	Node 9	Node 9	Node 9	Node 9
sum (s)	N/A	11	12	12

Key Moments - 3 Insights

Why do we move the left pointer forward when sum < target?

Because the BST is sorted in ascending order, moving the left pointer forward gives a larger value, increasing the sum closer to the target (see execution_table step 1).

Why do we stop when left pointer meets or passes right pointer?

Because all pairs have been checked; if no sum matched target by then, no valid pair exists (implied by the loop condition l < r).

How do the two pointers traverse the BST without extra sorting?

They use BST iterators: one moves in ascending order (left pointer), the other in descending order (right pointer), efficiently simulating a sorted array traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum at step 1?

A 12

B 9

C 11

D 2

💡 Hint

Check the 'Sum' column in execution_table row for step 1.

At which step does the function return True?

A Step 1

B Step 2

C Exit

D Never

💡 Hint

Look at the 'Action' column where sum equals target.

If the target was 15, what would happen to the left pointer after step 1?

A Move forward to next larger node

B Move backward to smaller node

C Stay at current node

D Function returns immediately

💡 Hint

Refer to the logic in concept_flow and execution_table step 1 where sum < target.

Concept Snapshot

Two Sum in BST:
- Use two pointers (iterators) on BST: one ascending, one descending
- Calculate sum of pointed nodes
- If sum == target, return True
- If sum < target, move left pointer forward
- If sum > target, move right pointer backward
- Stop when pointers meet or cross

Full Transcript

Two Sum in BST uses two pointers starting at smallest and largest nodes. We calculate their sum and compare to target. If sum matches target, we return True. If sum is less, we move the left pointer forward to increase sum. If sum is more, we move the right pointer backward to decrease sum. We repeat until pointers meet. This approach uses BST iterators to traverse nodes in sorted order without extra space for sorting.

Practice

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

easy

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

B. Find the maximum value in a BST

C. Check if a BST is balanced

D. Count the number of nodes in a BST

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 find if such a pair exists, not to find max value, check balance, or count nodes.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing with finding max/min value
• Thinking it checks BST balance
• Assuming it counts nodes

2. Which of the following Python code snippets correctly initializes an empty set to store visited node values in a Two Sum in BST solution?

easy

A. visited = []

B. visited = set()

C. visited = {}

D. visited = ()

Solution

1. Step 1: Identify correct set initialization syntax

   In Python, set() creates an empty set. Using [] creates a list, {} creates an empty dictionary, and () creates an empty tuple.

2. Step 2: Confirm usage for visited nodes

   We need a set to quickly check if a complement value exists, so visited = set() is correct.

3. Final Answer:

   visited = set() -> Option B

4. Quick Check:

   Empty set = set() [OK]

Hint: Use set() to create empty set, not {} or [] [OK]

Common Mistakes:

• Using [] which creates a list, not a set
• Using {} which creates a dict, not a set
• Using () which creates a tuple

3. Given the BST below and target = 9, what will the function find_target(root, 9) return?

BST structure:
5
/ \
3 6
/ \ \
2 4 7

Code snippet:

def find_target(root, k):
    visited = set()
    def dfs(node):
        if not node:
            return False
        if k - node.val in visited:
            return True
        visited.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Trace DFS traversal and visited set updates

   Start at root 5: visited = {}. Check if 9-5=4 in visited? No. Add 5.
   Go left to 3: check 9-3=6 in visited? No. Add 3.
   Go left to 2: check 9-2=7 in visited? No. Add 2.
   Left and right of 2 are None, return False.
   Back to 3, go right to 4: check 9-4=5 in visited? Yes (5 is in visited). Return True.

2. Step 2: Confirm function returns True

   Since a pair (5,4) sums to 9, function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Pair (5,4) found = True [OK]

Hint: Check complements in visited set during DFS [OK]

Common Mistakes:

• Not updating visited set before recursive calls
• Returning False too early
• Confusing node values and complements

4. Identify the bug in the following code for Two Sum in BST and select the correct fix.

def find_target(root, k):
    visited = set()
    def dfs(node):
        if not node:
            return False
        if node.val in visited:
            return True
        visited.add(k - node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

medium

A. Check if node.val in visited, add (k - node.val) to visited

B. Check if node.val in visited, add node.val to visited

C. Check if (k - node.val) in visited, add (k - node.val) to visited

D. Check if (k - node.val) in visited, add node.val to visited

Solution

1. Step 1: Understand the logic for Two Sum in BST

   We must check if the complement (k - current node value) exists in visited set. If yes, return True. Then add current node value to visited.

2. Step 2: Identify the bug in code

   The code incorrectly checks if node.val is in visited and adds (k - node.val) to visited. This reverses the logic and causes wrong results.

3. Step 3: Correct fix

   Check if (k - node.val) in visited, then add node.val to visited.

4. Final Answer:

   Check if (k - node.val) in visited, add node.val to visited -> Option D

5. Quick Check:

   Check complement in visited, add current value [OK]

Hint: Check complement in visited, add current value [OK]

Common Mistakes:

• Swapping check and add values
• Adding complement instead of current value
• Checking current value instead of complement

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 complexity?

hard

A. Check every pair of nodes by nested traversal (O(n²))

B. Use inorder traversal to get sorted list, then use two pointers to find sum

C. Use DFS with a hash set to check complements during traversal

D. Convert BST to a max heap and search pairs

Solution

1. Step 1: Analyze each approach

   Use DFS with a hash set to check complements during traversal: O(n) time and O(n) space.
   Use inorder traversal to get sorted list, then use two pointers to find sum: O(n) time and O(n) space.
   Check every pair of nodes by nested traversal (O(n²)): inefficient.
   Convert BST to a max heap and search pairs: unnecessary and costly.

2. Step 2: Choose the most efficient approach

   Both DFS with hash set and inorder + two pointers have O(n) time and space, but DFS with hash set uses less extra space by checking on the fly during traversal, avoiding full list creation.

3. Final Answer:

   Use DFS with a hash set to check complements during traversal -> Option C

4. Quick Check:

   DFS + hash set = efficient Two Sum in BST [OK]

Hint: Use DFS + hash set for O(n) time and space [OK]

Common Mistakes:

• Choosing nested loops causing O(n²) time
• Ignoring space complexity of inorder list
• Unnecessary BST conversions