Two Sum in BST in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum in BST with target 9

Given the BST below and target = 9, what is the output of the two_sum_in_bst function?

DSA Python

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

def two_sum_in_bst(root, target):
    seen = set()
    def dfs(node):
        if not node:
            return False
        if target - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

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

root = TreeNode(5,
                TreeNode(3, TreeNode(2), TreeNode(4)),
                TreeNode(6, None, TreeNode(7)))

print(two_sum_in_bst(root, 9))

A False

B Error

C None

D True

💡 Hint

Check if any two nodes sum up to 9 by traversing the tree and storing visited values.

The function finds two nodes with values 2 and 7 that sum to 9, so it returns True.

❓ Predict Output

intermediate

Output of Two Sum in BST with target 28

What is the output of the two_sum_in_bst function for the BST below and target = 28?

DSA Python

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

def two_sum_in_bst(root, target):
    seen = set()
    def dfs(node):
        if not node:
            return False
        if target - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

# BST structure:
#       10
#      /  \
#     5    15
#    / \     \
#   3   7     18

root = TreeNode(10,
                TreeNode(5, TreeNode(3), TreeNode(7)),
                TreeNode(15, None, TreeNode(18)))

print(two_sum_in_bst(root, 28))

A False

B True

C None

D Error

💡 Hint

Check if any two nodes sum up to 28 by traversing the tree and storing visited values.

The function finds two nodes with values 10 and 18 that sum to 28, so it returns True.

🔧 Debug

advanced

Identify the error in Two Sum in BST implementation

What error will this code raise when run?

DSA Python

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

def two_sum_in_bst(root, target):
    seen = set()
    def dfs(node):
        if not node:
            return False
        if target - node.val in seen:
            return True
        seen.add(node.val)
        return dfs(node.left) or dfs(node.right)
    return dfs(root)

root = TreeNode(1)
print(two_sum_in_bst(root, '3'))

A TypeError

B SyntaxError

C ValueError

D No error, returns False

💡 Hint

Check the types of target and node values during subtraction.

Subtracting string '3' and int node.val causes a TypeError.

🧠 Conceptual

advanced

Why use a set in Two Sum in BST?

Why does the two_sum_in_bst function use a set to store seen values?

A To store duplicate values multiple times

B To keep the values sorted for binary search

C To quickly check if the complement value exists in O(1) time

D To traverse the tree in order

💡 Hint

Think about how to check if a number exists efficiently.

A set allows fast lookup to check if the complement of the current node's value has been seen before.

🚀 Application

expert

Number of pairs summing to target in BST

Given the BST below and target = 10, how many unique pairs of nodes sum to the target?

DSA Python

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

def count_pairs_in_bst(root, target):
    seen = set()
    pairs = set()
    def dfs(node):
        if not node:
            return
        complement = target - node.val
        if complement in seen and (min(node.val, complement), max(node.val, complement)) not in pairs:
            pairs.add((min(node.val, complement), max(node.val, complement)))
        seen.add(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return len(pairs)

# BST structure:
#       5
#      / \
#     3   7
#    / \   \
#   2   4   8

root = TreeNode(5,
                TreeNode(3, TreeNode(2), TreeNode(4)),
                TreeNode(7, None, TreeNode(8)))

print(count_pairs_in_bst(root, 10))

A 2

B 3

C 1

D 0

💡 Hint

Find pairs like (2,8) and (3,7) that sum to 10.

Pairs (2,8) and (3,7) sum to 10, so the count is 2.

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