Two Sum in BST in DSA Rust - Execution Trace

Concept Flow - Two Sum in BST

Start at root

↓

Initialize empty set

↓

Inorder traversal node

↓

Check if (target - node.val) in set?

↓

Return true

↓

Move to next node

↓

Repeat until all nodes visited

↓

Return false if no pair found

Traverse the BST in order, checking if complement of current node value exists in a set; if yes, return true, else add current value and continue.

Execution Sample

DSA Rust

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

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

This code checks if there exist two values in the BST that sum to k by traversing in order and using a set to track complements.

Execution Table

Step	Operation	Current Node	Set Contents	Check Complement	Visual BST State
1	Start at root	5	{}	No	5 / \ 3 6 / \ \ 2 4 7
2	Traverse left	3	{}	No	5 / \ 3 6 / \ \ 2 4 7
3	Traverse left	2	{}	No	5 / \ 3 6 / \ \ 2 4 7
4	Check complement	2	{}	No (7-2=5 not in set)	5 / \ 3 6 / \ \ 2 4 7
5	Add 2 to set	2	{2}	N/A	5 / \ 3 6 / \ \ 2 4 7
6	Back to 3	3	{2}	No (7-3=4 not in set)	5 / \ 3 6 / \ \ 2 4 7
7	Add 3 to set	3	{2,3}	N/A	5 / \ 3 6 / \ \ 2 4 7
8	Traverse right	4	{2,3}	Yes (7-4=3 in set)	5 / \ 3 6 / \ \ 2 4 7
9	Return true	4	{2,3}	Found pair (3,4)	5 / \ 3 6 / \ \ 2 4 7

💡 Found two nodes (3 and 4) whose sum is 7, so return true.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 8	Final
set	{}	{}	{2,3}	{2,3}	{2,3}
current_node	5	2	3	4	4
found_pair	false	false	false	true	true

Key Moments - 3 Insights

Why do we check if (target - node.val) is in the set before adding node.val?

Because we want to find if a previously visited node complements the current node to sum to target. See execution_table step 8 where complement 3 is found in set before adding 4.

Why do we use inorder traversal for this problem?

Inorder traversal visits nodes in ascending order, but the order is not critical here. The key is visiting all nodes once. The set tracks visited values regardless of order. See execution_table steps 2-8.

What happens if the BST is empty?

The traversal immediately returns false because there are no nodes to check. This is implied by the base case in the code and no rows in execution_table beyond step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the content of the set?

A {2}

B {2,3}

C {}

D {3}

💡 Hint

Check the 'Set Contents' column at step 6 in execution_table.

At which step does the algorithm find the pair that sums to the target?

A Step 4

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'Check Complement' column where it says 'Yes' for the first time.

If the target was 14 instead of 7, what would happen in the execution_table?

A The algorithm would find a pair at step 8.

B The algorithm would return false after visiting all nodes.

C The set would remain empty.

D The algorithm would stop at step 4.

💡 Hint

Think about whether any two nodes sum to 14 in the given BST.

Concept Snapshot

Two Sum in BST:
- Traverse BST nodes (inorder or any order)
- Keep a set of visited node values
- For each node, check if (target - node.val) is in set
- If yes, return true
- Else add node.val to set and continue
- Return false if no pair found

Full Transcript

This visualization shows how to find two numbers in a binary search tree that add up to a target sum. We start at the root and traverse the tree in order. At each node, we check if the complement (target minus current node value) is already in a set of visited values. If it is, we found a pair and return true. Otherwise, we add the current node value to the set and continue. The execution table tracks each step, showing the current node, the set contents, and whether the complement check succeeds. The variable tracker shows how the set and current node change over time. Key moments clarify why we check the complement before adding the current value and what happens if the tree is empty. The quiz tests understanding of set contents and when the pair is found. This method efficiently finds the two sum pair in O(n) time and O(n) space.

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