Two Sum in BST in DSA Python - Deep Dive

Overview - Two Sum in BST

What is it?

Two Sum in BST is a problem where you find if there are two numbers in a Binary Search Tree (BST) that add up to a given target number. A BST is a special tree where left children are smaller and right children are bigger than their parent. The goal is to check if any two nodes in this tree sum to the target.

Why it matters

This problem helps us understand how to search and combine data efficiently in a sorted structure like a BST. Without this concept, searching pairs in a tree would be slow and complicated, making many applications like finding pairs in sorted data or checking sums in hierarchical data inefficient.

Where it fits

Before this, you should know what a Binary Search Tree is and how to traverse it. After this, you can learn more complex tree problems like balancing BSTs or finding paths with certain sums.

Mental Model

Core Idea

Find two numbers in a sorted tree that add up to a target by smartly searching from both ends.

Think of it like...

It's like having a sorted list of prices in a store and trying to find two items that together cost exactly your gift card amount by looking from the cheapest and most expensive items inward.

BST Structure and Two Pointer Search:

       5
      / \
     3   8
    / \   \
   2   4   10

Inorder traversal (sorted): 2 -> 3 -> 4 -> 5 -> 8 -> 10

Two pointers start:
Left pointer at 2 (smallest), Right pointer at 10 (largest)
Move pointers inward based on sum compared to target.

Build-Up - 6 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure keeps values sorted.

A Binary Search Tree is a tree where each node has up to two children. The left child has a smaller value, and the right child has a larger value than the node. This property makes searching fast because you can decide to go left or right depending on the value you want.

Result

You can quickly find if a value exists by comparing and moving left or right.

Understanding BST structure is key because it allows efficient searching and ordered traversal, which is the foundation for solving Two Sum in BST.

2

Foundation

Inorder Traversal Produces Sorted Values

Concept: Learn how to get all BST values in sorted order using inorder traversal.

Inorder traversal visits nodes in this order: left child, current node, right child. For BST, this means visiting values from smallest to largest. For example, for the BST: 5 / \ 3 8 / \ \ 2 4 10 The inorder traversal is: 2, 3, 4, 5, 8, 10.

Result

You get a sorted list of all values in the BST.

Knowing inorder traversal gives sorted data lets us apply two-pointer techniques that work on sorted lists.

3

Intermediate

Two Pointer Technique on Sorted Data

🤔Before reading on: Do you think starting pointers at both ends of a sorted list helps find pairs summing to target faster than checking all pairs? Commit to yes or no.

Concept: Use two pointers at the start and end of a sorted list to find two numbers that sum to a target efficiently.

Start with one pointer at the smallest number and one at the largest. Calculate their sum. If sum equals target, done. If sum is less than target, move the left pointer right to increase sum. If sum is more, move the right pointer left to decrease sum. Repeat until pointers meet.

Result

You find the pair in O(n) time instead of O(n²).

This technique reduces the search space by using the sorted order to decide pointer moves, making the search efficient.

4

Intermediate

Applying Two Pointers Directly on BST

🤔Before reading on: Can we apply two pointers directly on BST nodes without converting to a list? Commit to yes or no.

Concept: Use two iterators that traverse the BST in ascending and descending order to simulate two pointers without extra space.

We can create two iterators: one that does inorder traversal (smallest to largest) and one that does reverse inorder traversal (largest to smallest). Each iterator gives the next smallest or largest value on demand. We then compare sums from these iterators like two pointers.

Result

We find the pair without storing all values, saving memory.

Using BST iterators simulates two pointers efficiently, combining BST properties and two-pointer logic.

5

Advanced

Implementing BST Iterators for Two Sum

🤔Before reading on: Do you think using stacks to implement BST iterators is necessary for controlled traversal? Commit to yes or no.

Concept: Use stacks to implement controlled inorder and reverse inorder traversal iterators for BST.

Each iterator uses a stack to remember nodes. For inorder iterator, push all left children first. When next() is called, pop from stack, push right child's left children. For reverse iterator, push all right children first, then pop and push left child's right children. This way, next() returns next smallest or largest value.

Result

We get next values in O(h) time where h is tree height, with O(h) space.

Stacks allow controlled traversal without recursion, enabling efficient iterator design for two-pointer simulation.

6

Expert

Handling Edge Cases and Performance Tradeoffs

🤔Before reading on: Is it always better to use iterators over list conversion for Two Sum in BST? Commit to yes or no.

Concept: Understand when to use iterator approach vs list conversion and how to handle duplicates or unbalanced trees.

Converting BST to a list is simpler but uses O(n) space. Iterators use O(h) space but are more complex. For very unbalanced trees, h can approach n. Also, duplicates require careful pointer movement to avoid using the same node twice. Choosing approach depends on tree size, balance, and memory constraints.

Result

You can pick the best method for your situation and avoid bugs with duplicates.

Knowing tradeoffs and edge cases helps write robust, efficient solutions in real-world scenarios.

Under the Hood

The Two Sum in BST problem uses the BST's sorted property via inorder traversal. Internally, the iterators use stacks to simulate controlled traversal without recursion. The two-pointer logic compares values from smallest and largest ends, moving inward by popping and pushing nodes on stacks. This avoids full list creation and leverages BST structure for efficient search.

Why designed this way?

BSTs were designed to keep data sorted for fast search. Using inorder traversal exploits this order. The iterator design with stacks avoids recursion overhead and large memory use. Two-pointer technique is a classic efficient method for sorted data, adapted here to work directly on BST nodes.

BST Two Iterator Mechanism:

Inorder Iterator (Left to Right):
Stack: push left children down to smallest
Next(): pop top, push right child's left children

Reverse Iterator (Right to Left):
Stack: push right children down to largest
Next(): pop top, push left child's right children

Compare values from both iterators:
If sum < target: advance inorder iterator
If sum > target: advance reverse iterator
If sum == target: found pair

Stop when iterators meet.

Myth Busters - 3 Common Misconceptions

Quick: Does converting BST to a list always use less memory than using iterators? Commit to yes or no.

Common Belief: Converting BST to a list is always better because it's simpler and uses less memory.

Reality: Converting to a list uses O(n) memory, which can be large. Iterators use O(h) memory, which is smaller for balanced trees.

Why it matters: Using list conversion on large trees can cause high memory use and slow performance, while iterators keep memory low.

Quick: Can you use the same node twice in Two Sum in BST? Commit to yes or no.

Common Belief: You can use the same node twice if its value times two equals the target.

Reality: You must use two different nodes; using the same node twice is not allowed.

Why it matters: Allowing the same node twice leads to incorrect answers and bugs in the solution.

Quick: Does the two-pointer technique work on any tree traversal order? Commit to yes or no.

Common Belief: Two-pointer technique works on any traversal order of a BST.

Reality: It only works on sorted order, which is given by inorder traversal, not preorder or postorder.

Why it matters: Using wrong traversal order breaks the sorted property, making two-pointer logic invalid.

Expert Zone

1

BST iterators can be paused and resumed, allowing partial traversal and saving computation.

2

In unbalanced BSTs, iterator space can approach O(n), so balancing or alternative data structures may be better.

3

Handling duplicates requires careful pointer movement to avoid counting the same value twice from the same node.

When NOT to use

Avoid using BST iterators for Two Sum if the tree is very unbalanced or very large and memory is not a concern; converting to a sorted list might be simpler. For dynamic data with frequent inserts/deletes, balanced BSTs or hash-based sets may be better.

Production Patterns

In real systems, Two Sum in BST is used in database indexing, range queries, and memory-efficient search algorithms. Professionals often combine BST iterators with caching or balancing to optimize performance.

Connections

Two Sum in Sorted Array

Two Sum in BST builds on the same two-pointer technique used in sorted arrays.

Understanding Two Sum in arrays helps grasp the BST version since BST inorder traversal produces a sorted sequence.

Iterator Design Pattern

BST iterators for Two Sum use the iterator design pattern to traverse data on demand.

Knowing iterator patterns helps implement efficient, lazy traversal without extra memory.

Financial Budgeting

Finding two expenses that sum to a budget limit is similar to Two Sum in BST problem.

Recognizing this helps apply algorithmic thinking to everyday money management and vice versa.

Common Pitfalls

#1 Using preorder traversal to get values and then applying two-pointer technique.

Wrong approach:

def preorder(root):
return [root.val] + preorder(root.left) + preorder(root.right) if root else []

values = preorder(root)
left, right = 0, len(values)-1
while left < right:
s = values[left] + values[right]
if s == target:
return True
elif s < target:
left += 1
else:
right -= 1
return False

Correct approach:

def inorder(root):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []

values = inorder(root)
left, right = 0, len(values)-1
while left < right:
s = values[left] + values[right]
if s == target:
return True
elif s < target:
left += 1
else:
right -= 1
return False

Root cause:

Preorder traversal does not produce sorted values, breaking the two-pointer logic that requires sorted input.

#2 Using the same node twice when its value times two equals the target.

Wrong approach:

def two_sum_bst(root, target):
values = inorder(root)
for v in values:
if target - v in values:
return True
return False

Correct approach:

def two_sum_bst(root, target):
values = inorder(root)
left, right = 0, len(values) - 1
while left < right:
s = values[left] + values[right]
if s == target:
return True
elif s < target:
left += 1
else:
right -= 1
return False

Root cause:

Checking if target - v is in values without ensuring different nodes allows counting the same node twice.

#3 Converting BST to list for very large trees causing memory issues.

Wrong approach:

def two_sum_bst(root, target):
values = inorder(root) # uses O(n) memory
# rest of two-pointer code
...

Correct approach:

Use BST iterators with stacks to traverse on demand, keeping memory to O(h) where h is tree height.

Root cause:

Not considering memory constraints leads to inefficient solutions on large data.

Key Takeaways

Two Sum in BST finds if two nodes sum to a target by leveraging BST's sorted order.

Inorder traversal produces sorted values, enabling efficient two-pointer search.

BST iterators simulate two pointers without extra memory by controlled traversal using stacks.

Handling duplicates and tree balance is crucial for correct and efficient solutions.

Choosing between list conversion and iterators depends on tree size, memory, and complexity tradeoffs.

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