Two Sum in BST in DSA Python

Mental Model

We want to find two numbers in a tree that add up to a target. We use the tree's order to check pairs efficiently.

Analogy: Imagine a sorted list of prices in a store. You want to find two items that together cost exactly your budget. Instead of checking all pairs, you look from the cheapest and the most expensive, moving inward to find the perfect pair.

    5
   / \
  3   7
 / \   \
2   4   8

↑ root at 5

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, target = 9

Goal: Find if two nodes in BST sum to 9

Step 1: Initialize two pointers: one at smallest (2), one at largest (8)

Left pointer at 2, Right pointer at 8

Why: Start checking pairs from smallest and largest values

Step 2: Sum 2 + 8 = 10, which is greater than 9, move right pointer to next smaller (7)

Left pointer at 2, Right pointer at 7

Why: Sum too big, decrease right pointer to reduce sum

Step 3: Sum 2 + 7 = 9, found target sum

Left pointer at 2, Right pointer at 7

Why: Sum matches target, solution found

Result:

2 -> ... -> 7 -> null
Answer: True (2 + 7 = 9)

Annotated Code

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root, forward=True):
        self.stack = []
        self.forward = forward
        self._push_all(root)

    def _push_all(self, node):
        while node:
            self.stack.append(node)
            node = node.left if self.forward else node.right

    def has_next(self):
        return len(self.stack) > 0

    def next(self):
        node = self.stack.pop()
        val = node.val
        if self.forward:
            self._push_all(node.right)
        else:
            self._push_all(node.left)
        return val

def find_target(root, k):
    if not root:
        return False
    left_iter = BSTIterator(root, forward=True)   # smallest to largest
    right_iter = BSTIterator(root, forward=False) # largest to smallest

    left_val = left_iter.next() if left_iter.has_next() else None
    right_val = right_iter.next() if right_iter.has_next() else None

    while left_val is not None and right_val is not None and left_val < right_val:
        current_sum = left_val + right_val
        if current_sum == k:
            return True
        elif current_sum < k:
            if left_iter.has_next():
                left_val = left_iter.next()  # increase sum
            else:
                break
        else:
            if right_iter.has_next():
                right_val = right_iter.next()  # decrease sum
            else:
                break
    return False

# Driver code
root = TreeNode(5)
root.left = TreeNode(3, TreeNode(2), TreeNode(4))
root.right = TreeNode(7, None, TreeNode(8))

print(find_target(root, 9))

left_iter = BSTIterator(root, forward=True) # smallest to largest

initialize iterator to get next smallest values

right_iter = BSTIterator(root, forward=False) # largest to smallest

initialize iterator to get next largest values

while left_val is not None and right_val is not None and left_val < right_val:

loop until pointers cross or no more nodes

if current_sum == k:

check if current pair sums to target

elif current_sum < k:

sum too small, move left pointer forward to increase sum

else:

sum too big, move right pointer backward to decrease sum

Output

True

Complexity Analysis

Time: O(n) because in worst case we may visit all nodes once with two iterators

Space: O(h) where h is tree height, due to stacks used in iterators for traversal

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST order to reduce to O(n)

Edge Cases

Empty tree

Returns False immediately, no nodes to sum

DSA Python

if not root:
        return False

Single node tree

Returns False because we need two distinct nodes

DSA Python

while left_val is not None and right_val is not None and left_val < right_val:

No two nodes sum to target

Returns False after exhausting all pairs

DSA Python

return False

When to Use This Pattern

When asked to find two elements summing to a target in a BST, use two iterators from smallest and largest to find pairs efficiently.

Common Mistakes

Mistake: Using inorder traversal to create a list and then using two pointers on the list without considering space cost
Fix: Use BST iterators to traverse on the fly and save space

Mistake: Not checking that left pointer is less than right pointer, causing incorrect results or infinite loops
Fix: Add condition left_val < right_val in the loop to avoid crossing pointers

Summary

Finds if two nodes in a BST sum to a given target using two-pointer technique with iterators.

Use when you need to check pair sums efficiently in a BST without extra space for full traversal.

The key insight is to use two BST iterators moving inward from smallest and largest values to find the sum.

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