Two Sum in BST in DSA Python - Build from Scratch

Two Sum in BST

📖 Scenario: You are working with a phone book stored as a Binary Search Tree (BST). Each node contains a phone number. You want to find if there are two phone numbers in the BST that add up to a specific target sum.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target sum, and checks if any two numbers in the BST add up to that target.

📋 What You'll Learn

Create a BST with exact phone numbers as nodes

Set a target sum variable

Implement a function to check if two numbers in the BST add up to the target

Print True if such a pair exists, otherwise False

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that add up to a target is common in financial applications, phone number analysis, and data validation.

💼 Career

Understanding tree traversal and set usage is important for software engineers working with data structures and algorithms in interviews and real projects.

1

Create the BST with given phone numbers

Create a class called Node with val, left, and right attributes. Then create the BST root node with value 10. Add left child node with value 5 and right child node with value 15. Add left child of node 5 with value 3 and right child of node 5 with value 7. Add right child of node 15 with value 18.

DSA Python

# Define Node class and create BST nodes as described
# Your code here

Hint

Start by defining a simple Node class with value and two children. Then create nodes exactly as instructed to form the BST.

2

Set the target sum to find

Create a variable called target and set it to 20.

DSA Python

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

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

# Set the target sum to 20
# Your code here

Hint

Just create a variable named target and assign the number 20 to it.

3

Implement function to check two sum in BST

Define a function called find_target that takes root and k as parameters. Use a set called seen to store visited node values. Traverse the BST using a helper function dfs that visits nodes in any order. For each node, check if k - node.val is in seen. If yes, return True. Otherwise, add node.val to seen and continue. Return False if no pair found.

DSA Python

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

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

target = 20

# Define find_target function below
# Your code here

Hint

Use a helper function to walk through the tree. Keep track of values seen in a set. Check if the complement to the target exists in the set.

4

Print the result of two sum check

Print the result of calling find_target with root and target.

DSA Python

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

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

target = 20

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

# Print the result of find_target(root, target)
# Your code here

Hint

Just print the result of find_target(root, target). It should print True because 7 + 13 (not in tree) is not valid, but 5 + 15 = 20 is valid.

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