Two Sum in BST in DSA Rust

Mental Model

We want to find two numbers in a tree that add up to a target. We use the tree's order to check pairs efficiently.

Analogy: Imagine a sorted list of prices in a store. You want to find two items that together cost exactly your budget. Instead of checking all pairs, you look from the cheapest and the most expensive items moving inward.

    5
   / \
  3   7
 / \   \
2   4   8

We want to find two nodes whose values add up to target.

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, target = 9

Goal: Find if there exist two nodes in BST whose values sum to 9

Step 1: Initialize two pointers: left at smallest (2), right at largest (8)

Left -> 2, Right -> 8

Why: Start checking pairs from smallest and largest values

Step 2: Sum left + right = 2 + 8 = 10, which is greater than 9, move right pointer to next smaller value

Left -> 2, Right -> 7

Why: Sum too big, decrease right to reduce sum

Step 3: Sum left + right = 2 + 7 = 9, equals target, found the pair

Left -> 2, Right -> 7

Why: Sum matches target, stop search

Result:

2 -> 7 sum to 9

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

// Iterator for BST in ascending or descending order
struct BSTIterator {
    stack: Vec<Rc<RefCell<TreeNode>>>,
    forward: bool,
}

impl BSTIterator {
    fn new(root: Option<Rc<RefCell<TreeNode>>>, forward: bool) -> Self {
        let mut it = BSTIterator { stack: Vec::new(), forward };
        it.push_all(root);
        it
    }

    fn push_all(&mut self, mut node: Option<Rc<RefCell<TreeNode>>>) {
        while let Some(n) = node {
            self.stack.push(n.clone());
            node = if self.forward {
                n.borrow().left.clone()
            } else {
                n.borrow().right.clone()
            };
        }
    }

    fn next(&mut self) -> Option<i32> {
        if let Some(node) = self.stack.pop() {
            let val = node.borrow().val;
            if self.forward {
                self.push_all(node.borrow().right.clone());
            } else {
                self.push_all(node.borrow().left.clone());
            }
            Some(val)
        } else {
            None
        }
    }
}

fn find_target(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> bool {
    if root.is_none() {
        return false;
    }
    let mut left_iter = BSTIterator::new(root.clone(), true); // ascending
    let mut right_iter = BSTIterator::new(root.clone(), false); // descending

    let mut left_val = left_iter.next();
    let mut right_val = right_iter.next();

    while left_val.is_some() && right_val.is_some() && left_val.unwrap() < right_val.unwrap() {
        let sum = left_val.unwrap() + right_val.unwrap();
        if sum == k {
            return true;
        } else if sum < k {
            left_val = left_iter.next(); // increase sum
        } else {
            right_val = right_iter.next(); // decrease sum
        }
    }
    false
}

fn main() {
    // Build BST: 5 / \ 3 7 / \   \ 2 4   8
    let root = TreeNode::new(5);
    let node3 = TreeNode::new(3);
    let node7 = TreeNode::new(7);
    let node2 = TreeNode::new(2);
    let node4 = TreeNode::new(4);
    let node8 = TreeNode::new(8);

    root.borrow_mut().left = Some(node3.clone());
    root.borrow_mut().right = Some(node7.clone());
    node3.borrow_mut().left = Some(node2.clone());
    node3.borrow_mut().right = Some(node4.clone());
    node7.borrow_mut().right = Some(node8.clone());

    let target = 9;
    let found = find_target(Some(root), target);
    println!("{}", found);
}

let mut left_iter = BSTIterator::new(root.clone(), true); // ascending

initialize iterator to get smallest values first

let mut right_iter = BSTIterator::new(root.clone(), false); // descending

initialize iterator to get largest values first

while left_val.is_some() && right_val.is_some() && left_val.unwrap() < right_val.unwrap() {

loop while pointers do not cross

let sum = left_val.unwrap() + right_val.unwrap();

calculate sum of current pair

if sum == k { return true; } else if sum < k { left_val = left_iter.next(); } else { right_val = right_iter.next(); }

move left pointer forward if sum too small, right pointer backward if sum too big

Output

true

Complexity Analysis

Time: O(n) because in worst case we may visit all nodes once with two iterators

Space: O(h) where h is tree height due to stack space in iterators

vs Alternative: Naive approach checks all pairs O(n^2), this uses BST order to reduce to O(n)

Edge Cases

empty tree

returns false immediately

DSA Rust

if root.is_none() { return false; }

single node tree

returns false because cannot form pair

DSA Rust

while left_val.is_some() && right_val.is_some() && left_val.unwrap() < right_val.unwrap()

no two nodes sum to target

returns false after exhausting pairs

DSA Rust

return false at end of find_target

When to Use This Pattern

When asked to find two values summing to target in a BST, use two-pointer iteration from smallest and largest values to find pairs efficiently.

Common Mistakes

Mistake: Trying to convert BST to array first, losing O(h) space advantage
Fix: Use BST iterators to traverse in order without full conversion

Mistake: Not stopping when pointers cross, causing incorrect results or infinite loop
Fix: Stop loop when left pointer value is not less than right pointer value

Summary

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

Use when you want to check pairs in BST efficiently without extra space for full traversal.

Use two iterators from smallest and largest values moving inward to find the pair.

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