Two Sum in BST in DSA Rust - 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 efficiently search and combine data in a sorted structure like a BST. Without this concept, checking pairs would be slow and wasteful, especially for large trees. It shows how tree properties can speed up searching for pairs, which is useful in many real-world tasks like finding matching pairs in sorted data.

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 trees or finding paths with certain sums.

Mental Model

Core Idea

Use the BST's sorted nature to find two nodes whose values add up to the target by searching from both ends simultaneously.

Think of it like...

Imagine you have a sorted list of prices on a shelf, and you want to find two items that together cost exactly your budget. You start checking from the cheapest and the most expensive items, moving inward until you find the perfect pair or run out of options.

BST Inorder Traversal (sorted):
[ 1, 3, 4, 6, 7, 8, 10 ]

Two pointers approach:
  left -> 1
  right -> 10

Check sum = 1 + 10 = 11
If sum > target, move right pointer left
If sum < target, move left pointer right
Repeat until pointers meet or sum found

Build-Up - 6 Steps

1

Foundation

Understanding Binary Search Trees

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 means if you visit nodes in order (left, node, right), you get values sorted from smallest to largest.

Result

You can get a sorted list of values by doing an inorder traversal of the BST.

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 to Get Sorted Values

Concept: Learn how to visit BST nodes in sorted order using inorder traversal.

Inorder traversal means: 1. Visit left subtree 2. Visit current node 3. Visit right subtree This visits nodes from smallest to largest value in a BST. Example: For BST with nodes 4, 2, 6, 1, 3, 5, 7, inorder traversal outputs: 1, 2, 3, 4, 5, 6, 7

Result

You get a sorted list of all node values from the BST.

Knowing inorder traversal gives you a sorted list, which is essential for applying the two-pointer technique to find pairs.

3

Intermediate

Two-Pointer Technique on Sorted List

🤔Before reading on: do you think starting pointers at both ends or both at the start is better for finding two numbers that sum to target? Commit to your answer.

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

Given a sorted list, place one pointer at the start (smallest value) and one at the end (largest value). Calculate sum of values at pointers: - If sum equals target, pair found. - If sum is less than target, move start pointer right to increase sum. - If sum is greater than target, move end pointer left to decrease sum. Repeat until pointers meet or pair found.

Result

You find if a pair exists in O(n) time without checking every pair.

This technique leverages sorted order to skip unnecessary checks, making pair search much faster.

4

Intermediate

Applying Two-Pointer Technique to BST

🤔Before reading on: do you think converting BST to list first or searching directly in BST is simpler? Commit to your answer.

Concept: Combine inorder traversal and two-pointer technique to find two sum in BST by first getting sorted values.

Step 1: Perform inorder traversal to get sorted list of BST values. Step 2: Use two-pointer technique on this list to find if two values sum to target. This approach is simple and uses BST properties but requires extra space for the list.

Result

You can find if two sum exists in BST in O(n) time and O(n) space.

Converting BST to sorted list simplifies the problem to a known pattern, making it easier to implement and understand.

5

Advanced

Optimized Two Sum Without Extra Space

🤔Before reading on: do you think it's possible to find two sum in BST without storing all values? Commit to yes or no.

Concept: Use two iterators on BST to simulate two pointers without extra list storage, saving memory.

Instead of storing all values, create two iterators: - One does inorder traversal (smallest to largest). - One does reverse inorder traversal (largest to smallest). Advance iterators similar to two-pointer technique: - If sum < target, move inorder iterator forward. - If sum > target, move reverse iterator backward. Stop when iterators meet or pair found. This uses O(h) space where h is tree height, better than O(n).

Result

You find two sum in BST efficiently with less memory.

Knowing how to traverse BST from both ends simultaneously avoids extra space and is a clever use of BST properties.

6

Expert

Handling Edge Cases and Large Trees

🤔Before reading on: do you think duplicate values in BST affect two sum results? Commit to yes or no.

Concept: Consider duplicates, tree balance, and iterator synchronization to ensure correctness and performance.

Duplicates: If BST allows duplicates, ensure iterators don't point to the same node twice unless allowed. Unbalanced Trees: Height h can be large, so iterator stack space can grow. Iterator Sync: Carefully advance iterators to avoid infinite loops or missing pairs. Example: For target 10 in BST with duplicates 5, 5, ensure pair (5,5) is counted once. Testing with skewed trees ensures robustness.

Result

Your solution works correctly and efficiently in all BST shapes and with duplicates.

Handling these details prevents subtle bugs and ensures your solution is production-ready.

Under the Hood

The BST stores values so that left subtree nodes are smaller and right subtree nodes are larger. Inorder traversal uses recursion or a stack to visit nodes in ascending order. Two iterators simulate two pointers by maintaining stacks of nodes to traverse next smallest or largest values. They advance by popping nodes and pushing children, maintaining O(h) space where h is tree height.

Why designed this way?

BSTs were designed to allow fast search, insert, and delete operations by keeping data sorted in a tree structure. Using inorder traversal leverages this sorted order. The two-pointer technique is a classic approach for sorted arrays, adapted here to BSTs to avoid extra space. This design balances time and space efficiency.

BST Structure:
       6
      / \
     3   8
    / \   \
   1   4   10

Inorder Iterator Stack (left to right):
[1, 3, 4, 6, 8, 10]

Reverse Inorder Iterator Stack (right to left):
[10, 8, 6, 4, 3, 1]

Two iterators move inward:
left -> 1, right -> 10
Check sum, move pointers accordingly

Myth Busters - 3 Common Misconceptions

Quick: Do you think you must convert the BST to a list before finding two sum? Commit yes or no.

Common Belief: You must convert the BST to a sorted list first to find two sum.

Reality: You can find two sum directly using two BST iterators without full list conversion.

Why it matters: Converting to a list uses extra memory and can be slow for large trees; avoiding it improves performance.

Quick: Do you think the two-pointer technique works if the BST is not a binary search tree? Commit yes or no.

Common Belief: Two-pointer technique works on any binary tree.

Reality: It only works on BSTs because their inorder traversal produces sorted values.

Why it matters: Applying two-pointer on unsorted data leads to incorrect results and wasted effort.

Quick: Do you think duplicates in BST always cause incorrect two sum results? Commit yes or no.

Common Belief: Duplicates always break two sum solutions in BST.

Reality: Duplicates can be handled carefully by checking node identities and iterator positions.

Why it matters: Ignoring duplicates can cause missed pairs or false positives, leading to wrong answers.

Expert Zone

1

Two BST iterators must maintain their own stacks and carefully manage node visits to avoid overlap or skipping nodes.

2

The space complexity depends on tree height, so balanced BSTs are more memory efficient for this approach than skewed trees.

3

When target is twice a node's value, ensure the two iterators do not point to the same node unless duplicates exist.

When NOT to use

If the BST is very large and memory is extremely limited, or if the tree is not balanced, consider using hashing with traversal to find pairs instead. Also, if the tree is not a BST, use other methods like hash sets on traversal.

Production Patterns

In real systems, this pattern is used in database indexing to quickly find pairs matching criteria. Also used in memory-efficient search algorithms where data is stored in trees, such as file systems or search engines.

Connections

Two Sum in Sorted Array

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

Understanding two-pointer in arrays helps grasp the BST approach since BST inorder traversal produces a sorted sequence.

Iterator Design Pattern

The BST two-pointer solution uses two iterators to traverse the tree from opposite ends.

Knowing iterator patterns helps implement efficient traversal without extra memory, a common technique in software design.

Database Indexing

BSTs are similar to B-trees used in databases for indexing and searching data efficiently.

Understanding BST two sum helps appreciate how databases find matching records quickly using tree structures.

Common Pitfalls

#1 Using inorder traversal to get values but forgetting to use two pointers, then checking all pairs with nested loops.

Wrong approach:

let values = inorder_traversal(&root);
for i in 0..values.len() {
for j in i+1..values.len() {
if values[i] + values[j] == target {
return true;
}
}
}
return false;

Correct approach:

let values = inorder_traversal(&root);
let mut left = 0;
let mut right = values.len() - 1;
while left < right {
let sum = values[left] + values[right];
if sum == target {
return true;
} else if sum < target {
left += 1;
} else {
right -= 1;
}
}
return false;

Root cause:

Not leveraging the sorted property to reduce time complexity from O(n^2) to O(n).

#2 Advancing both BST iterators without checking sum comparison, causing infinite loops or missed pairs.

Wrong approach:

while left_iter.has_next() && right_iter.has_next() {
let left_val = left_iter.next();
let right_val = right_iter.next();
if left_val + right_val == target {
return true;
}
}

Correct approach:

while left_val < right_val {
let sum = left_val + right_val;
if sum == target {
return true;
} else if sum < target {
left_val = left_iter.next();
} else {
right_val = right_iter.prev();
}
}

Root cause:

Not controlling iterator advancement based on sum comparison breaks the two-pointer logic.

#3 Assuming duplicates automatically mean a pair exists without checking node positions.

Wrong approach:

if node_value * 2 == target {
return true;
}

Correct approach:

Check if there are two distinct nodes with the same value before returning true for duplicates.

Root cause:

Confusing value equality with node identity leads to false positives.

Key Takeaways

Two Sum in BST uses the BST's sorted property to efficiently find pairs summing to a target.

Inorder traversal produces a sorted list of BST values, enabling the two-pointer technique.

Two BST iterators can simulate two pointers without extra space by traversing from smallest and largest values.

Handling duplicates and iterator synchronization is crucial for correctness in real-world BSTs.

This problem connects tree traversal, sorting, and searching techniques, building a strong foundation for advanced data structure problems.

Practice

1. What is the main goal of the Two Sum in BST problem?

easy

A. Find two nodes in the BST whose values add up to a target sum.

B. Find the maximum value in the BST.

C. Count the total number of nodes in the BST.

D. Check if the BST is balanced.

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: Clarify the goal

   We need to check if any pair of nodes exists with values summing to the target, not just find max or count nodes.

3. Final Answer:

   Find two nodes in the BST whose values add up to a target sum. -> Option A

4. Quick Check:

   Two Sum in BST = Find pair with target sum [OK]

Hint: Look for two values that add to target in BST [OK]

Common Mistakes:

• Thinking it asks for max value only
• Confusing with counting nodes
• Assuming BST must be balanced

2. Which Rust code snippet correctly defines a BST node struct for the Two Sum problem?

easy

A. struct TreeNode { val: i32, left: TreeNode, right: TreeNode }

B. struct TreeNode { val: i32, left: Option, right: Option }

C. struct TreeNode { val: i32, left: &TreeNode, right: &TreeNode }

D. struct TreeNode { val: i32, left: Option<TreeNode>, right: Option<TreeNode> }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Rust requires recursive types like BST nodes to use Box or other smart pointers to allocate on heap.

2. Step 2: Check each option

   struct TreeNode { val: i32, left: Option, right: Option } uses Option which is correct. struct TreeNode { val: i32, left: TreeNode, right: TreeNode } and D use direct TreeNode which is invalid recursive type. struct TreeNode { val: i32, left: &TreeNode, right: &TreeNode } uses references without lifetimes, which is incorrect.

3. Final Answer:

   struct TreeNode { val: i32, left: Option, right: Option } -> Option B

4. Quick Check:

   Use Box for recursive BST nodes in Rust [OK]

Hint: Use Option for recursive BST nodes [OK]

Common Mistakes:

• Using direct TreeNode type causing infinite size error
• Using references without lifetimes
• Omitting Option for nullable children

3. Given the following BST and target = 9, what will the Two Sum function return?

      5
     / \
    3   6
   / \   \
  2   4   7

Rust code snippet:

fn find_target(root: &Option, k: i32) -> bool {
    let mut set = std::collections::HashSet::new();
    fn dfs(node: &Option, k: i32, set: &mut std::collections::HashSet<i32>) -> bool {
        if let Some(n) = node {
            if set.contains(&(k - n.val)) {
                return true;
            }
            set.insert(n.val);
            dfs(&n.left, k, set) || dfs(&n.right, k, set)
        } else {
            false
        }
    }
    dfs(root, k, &mut set)
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace DFS with HashSet on BST nodes

   Start at root 5, set is empty. Check if complement 9-5=4 in set? No. Insert 5. Check left child 3: complement 9-3=6, 6 not in set. Insert 3. Check left 2: complement 9-2=7, 7 not in set. Insert 2. Check right 4: complement 9-4=5, 5 is in set, so return true.

2. Step 2: Confirm early return on finding pair

   Since pair (5,4) sums to 9, function returns true immediately.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pair found (5+4=9) = true [OK]

Hint: Check if complement exists in set during DFS [OK]

Common Mistakes:

• Not inserting current node before checking complement
• Returning false too early
• Ignoring left or right subtree

4. Identify the bug in this Rust function for Two Sum in BST:

fn find_target(root: &Option, k: i32) -> bool {
    let mut set = std::collections::HashSet::new();
    fn dfs(node: &Option, k: i32, set: &mut std::collections::HashSet<i32>) -> bool {
        if let Some(n) = node {
            set.insert(n.val);
            if set.contains(&(k - n.val)) {
                return true;
            }
            dfs(&n.left, k, set) || dfs(&n.right, k, set)
        } else {
            false
        }
    }
    dfs(root, k, &mut set)
}

medium

A. Function does not handle empty tree.

B. Missing return statement in dfs function.

C. HashSet is not imported correctly.

D. Inserting current node value before checking complement causes false positive.

Solution

1. Step 1: Analyze order of operations in DFS

   The code inserts current node value into set before checking if complement exists. This causes the complement check to always find current value itself, leading to false positive.

2. Step 2: Correct approach

   Check if complement exists in set first, then insert current node value to avoid matching node with itself.

3. Final Answer:

   Inserting current node value before checking complement causes false positive. -> Option D

4. Quick Check:

   Check complement before insert to avoid false positive [OK]

Hint: Check complement before inserting current value [OK]

Common Mistakes:

• Inserting before checking complement
• Ignoring early return on true
• Not handling None nodes

5. You want to optimize the Two Sum in BST problem to use O(h) space, where h is tree height. Which approach is best? A BST inorder iterator yields sorted values. How can you use two iterators to solve Two Sum efficiently?

hard

A. Use a HashSet to store visited nodes and check complements during DFS.

B. Traverse BST in preorder and store all values in a vector, then use two pointers on vector.

C. Use two iterators: one from smallest to largest, another from largest to smallest, moving inward to find target sum.

D. Convert BST to linked list and then check pairs sequentially.

Solution

1. Step 1: Understand space constraints and BST properties

   Storing all nodes uses O(n) space. Using BST inorder iterator yields sorted values with O(h) space.

2. Step 2: Use two iterators moving inward

   One iterator moves from smallest to largest (inorder), another from largest to smallest (reverse inorder). Compare sums and move iterators accordingly to find target sum efficiently.

3. Step 3: Compare with other options

   Traverse BST in preorder and store all values in a vector, then use two pointers on vector. uses O(n) space. Use a HashSet to store visited nodes and check complements during DFS. uses HashSet with O(n) space. Convert BST to linked list and then check pairs sequentially. is inefficient and uses extra space.

4. Final Answer:

   Use two iterators: one from smallest to largest, another from largest to smallest, moving inward to find target sum. -> Option C

5. Quick Check:

   Two BST iterators inward = O(h) space Two Sum [OK]

Hint: Use two BST iterators from ends moving inward [OK]

Common Mistakes:

• Using full traversal storing all nodes
• Ignoring space complexity
• Not using reverse inorder iterator