Why Two Sum in BST in DSA Python?

The Big Idea

What if you could find two numbers adding to a target in a sorted tree without checking every pair?

The Scenario

Imagine you have a large family photo album sorted by age, and you want to find two people whose ages add up to a specific number. Without any system, you would have to check every possible pair, flipping back and forth through pages.

The Problem

Manually checking every pair is slow and tiring. It's easy to miss pairs or check the same pair twice. This wastes time and causes frustration, especially with many people in the album.

The Solution

Using a Binary Search Tree (BST) and the Two Sum approach, you can quickly find if two ages add up to the target. The BST keeps ages sorted, and the Two Sum method smartly checks pairs without repeating or missing any.

Before vs After

✗ Before

ages = [10, 20, 30, 40]
target = 50
for i in range(len(ages)):
    for j in range(i+1, len(ages)):
        if ages[i] + ages[j] == target:
            print('Found')

✓ After

def find_two_sum_bst(root, target):
    # Use BST properties and two-pointer technique
    # to find if two nodes sum to target
    pass

What It Enables

This lets you quickly find pairs adding to a target in sorted data without checking every pair, saving time and effort.

Real Life Example

Finding two products in a sorted price list that together match a gift card value, without trying every combination.

Key Takeaways

Manual pair checking is slow and error-prone.

BST keeps data sorted for efficient searching.

Two Sum in BST finds pairs quickly and reliably.

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