Two Sum in BST in DSA C# - 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 child nodes are smaller and right child nodes 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 in a tree would be slow and complicated. It shows how to use the BST's order to find pairs quickly, which is useful in many real-world tasks like searching databases or solving puzzles.

Where it fits

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

Mental Model

Core Idea

Find two numbers in a sorted tree that add up to a target by efficiently searching from both ends towards the middle.

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 budget by looking from the cheapest and most expensive items inward.

BST Inorder Traversal (sorted):

  2 -> 5 -> 7 -> 10 -> 15 -> 20

Two pointers start:
  Left pointer at 2 (smallest)
  Right pointer at 20 (largest)

If sum < target, move left pointer right.
If sum > target, move right pointer left.
Repeat until pointers meet or sum found.

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 parent. This property helps us find values quickly by deciding to go left or right at each step.

Result

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

Understanding the BST property is key because it allows searching in O(log n) time instead of checking every node.

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 a BST, this means visiting nodes from smallest to largest value.

Result

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

Knowing that inorder traversal sorts the BST values lets us use two-pointer techniques on the resulting list.

3

Intermediate

Two-Pointer Technique on Sorted List

🤔Before reading on: do you think starting pointers at both ends of a sorted list helps find pairs 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. Add their values. If the sum is too small, move the left pointer right to increase sum. If too large, move the right pointer left to decrease sum. Repeat until pointers meet or sum matches target.

Result

You find if a pair exists in O(n) time instead of O(n^2).

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

4

Intermediate

Applying Two-Pointer Technique to BST

🤔Before reading on: do you think we must convert the BST to a list first or can we do two-pointer search directly on the tree? Commit to your answer.

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

Instead of converting the BST to a list, use two stacks to traverse the BST: one for the smallest values (inorder) and one for the largest values (reverse inorder). Move these iterators like pointers to find the target sum.

Result

You find the pair in O(n) time and O(h) space, where h is tree height, saving memory.

This approach uses BST properties and traversal techniques to avoid extra memory, making it efficient for large trees.

5

Advanced

Implementing Two Sum in BST in C#

🤔Before reading on: do you think using two stacks for traversal is more memory efficient than storing all values? Commit to yes or no.

Concept: Write C# code that uses two stacks to traverse the BST from both ends and find if two nodes sum to the target.

```csharp using System; using System.Collections.Generic; public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { this.val = val; this.left = left; this.right = right; } } public class Solution { public bool FindTarget(TreeNode root, int k) { if (root == null) return false; Stack leftStack = new Stack(); Stack rightStack = new Stack(); void PushLeft(TreeNode node) { while (node != null) { leftStack.Push(node); node = node.left; } } void PushRight(TreeNode node) { while (node != null) { rightStack.Push(node); node = node.right; } } PushLeft(root); PushRight(root); TreeNode GetNextLeft() { var node = leftStack.Pop(); PushLeft(node.right); return node; } TreeNode GetNextRight() { var node = rightStack.Pop(); PushRight(node.left); return node; } TreeNode leftNode = GetNextLeft(); TreeNode rightNode = GetNextRight(); while (leftNode != rightNode) { int sum = leftNode.val + rightNode.val; if (sum == k) return true; else if (sum < k) leftNode = GetNextLeft(); else rightNode = GetNextRight(); } return false; } } ```

Result

The method returns true if two nodes sum to the target, false otherwise.

Implementing two-pointer logic directly on BST traversal stacks avoids extra memory and keeps time efficient.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the two-pointer BST method works correctly if the BST has duplicate values? Commit to yes or no.

Concept: Consider duplicates, empty trees, and skewed trees to ensure the solution is robust and efficient.

Duplicates can cause the two pointers to meet on the same node, which should not count as two different nodes. The code stops when pointers meet to avoid this. Empty trees return false immediately. Skewed trees (like linked lists) degrade performance to O(n) but still work correctly.

Result

The solution correctly handles all edge cases and maintains O(n) time and O(h) space complexity.

Understanding edge cases prevents bugs and ensures the solution works in all real-world scenarios.

Under the Hood

The solution uses two controlled traversals of the BST: one in ascending order (inorder) and one in descending order (reverse inorder). Each traversal uses a stack to remember the path. By advancing these traversals step-by-step, it simulates two pointers moving through a sorted list without storing all values. This leverages the BST's sorted property and stack-based traversal to find pairs efficiently.

Why designed this way?

Storing all values in a list uses extra memory proportional to the number of nodes. Using two stacks keeps memory proportional to the tree height, which is smaller. This design balances time and space efficiency, making it practical for large trees. The approach builds on classic inorder traversal but cleverly adds a reverse traversal to simulate two pointers.

BST Traversal Stacks:

  Root
   │
 ┌─┴─┐
 │   │
LeftStack (inorder)       RightStack (reverse inorder)
  ┌─────┐                   ┌─────┐
  │ 2   │                   │ 20  │
  │ 5   │                   │ 15  │
  │ ... │                   │ ... │
  └─────┘                   └─────┘

Pointers move inward by popping from stacks and pushing next nodes.

Myth Busters - 4 Common Misconceptions

Quick: Do you think converting the BST to a list is always the best way to solve Two Sum? Commit yes or no.

Common Belief: Many believe converting the BST to a sorted list first is the simplest and best approach.

Reality: While converting works, it uses extra memory proportional to the number of nodes, which can be large. Using two stacks for traversal is more memory efficient.

Why it matters: Using extra memory can cause slowdowns or crashes with big trees, making the solution impractical.

Quick: Do you think the two-pointer method can use the same node twice to sum to the target? Commit yes or no.

Common Belief: Some think the same node can be counted twice if its value times two equals the target.

Reality: The solution must use two distinct nodes. The pointers stop when they meet to avoid using the same node twice.

Why it matters: Counting the same node twice leads to incorrect answers and bugs.

Quick: Do you think the two-pointer technique works without the BST being a valid BST? Commit yes or no.

Common Belief: People may think the method works on any binary tree.

Reality: The method relies on BST properties (sorted order). It fails or gives wrong results if the tree is not a BST.

Why it matters: Applying this method to non-BSTs can cause wrong answers and wasted effort.

Quick: Do you think the time complexity is always O(log n) because BSTs are fast? Commit yes or no.

Common Belief: Some believe searching pairs in BST is always very fast, like O(log n).

Reality: The worst-case time is O(n) because you may need to check many nodes, especially in skewed trees.

Why it matters: Expecting too fast performance can lead to surprises in large or unbalanced trees.

Expert Zone

1

The two-stack traversal simulates two pointers without flattening the tree, saving memory but requiring careful stack management.

2

The approach gracefully handles skewed trees by degrading to linear time but never worse, unlike naive methods.

3

Stopping when pointers meet avoids counting the same node twice, a subtle but critical correctness detail.

When NOT to use

Avoid this method if the tree is not a BST or if you need to find all pairs rather than just one. For non-BSTs, use hash sets or sorting arrays. For all pairs, a different approach with more memory or time is needed.

Production Patterns

In real systems, this method is used in database indexing where data is stored in BST-like structures. It helps quickly find pairs matching criteria without loading all data into memory. Also used in coding interviews to test understanding of BST traversal and two-pointer techniques.

Connections

Two Sum in Sorted Array

Builds-on

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

Iterator Pattern in Software Design

Same pattern

The two-stack traversal acts like two iterators moving through data in opposite directions, showing how design patterns apply to algorithmic problems.

Searching for Pairs in Social Networks

Analogous problem in different domain

Finding two users with combined attributes matching a target is like Two Sum in BST, showing how algorithms help in social network analysis.

Common Pitfalls

#1 Using the same node twice to form the sum.

Wrong approach:

if (leftNode.val + rightNode.val == target) return true; // without checking if leftNode != rightNode

Correct approach:

while (leftNode != rightNode) { if (leftNode.val + rightNode.val == target) return true; ... }

Root cause:

Not realizing that pointers can meet on the same node, which should not count as two distinct nodes.

#2 Converting BST to list and then using two pointers, causing high memory use.

Wrong approach:

List vals = new List(); Inorder(root, vals); // store all nodes
Use two pointers on vals

Correct approach:

Use two stacks to traverse BST directly without storing all nodes.

Root cause:

Not considering memory constraints and the BST property that allows traversal without full storage.

#3 Applying two-pointer method on a non-BST binary tree.

Wrong approach:

Use two stacks for inorder and reverse inorder on any binary tree without checking BST property.

Correct approach:

Ensure the tree is a BST before applying this method or use a hash set approach for general binary trees.

Root cause:

Assuming the tree is sorted when it is not, leading to incorrect results.

Key Takeaways

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

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

Using two stacks to traverse from smallest and largest values simulates two pointers without extra memory.

Careful handling of pointers prevents using the same node twice and ensures correctness.

This method balances time and space efficiency and is widely used in real-world systems.

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

   The goal is to check if such a pair exists, not to find max, count nodes, or check balance.

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 adding to target in BST nodes [OK]

Common Mistakes:

• Confusing with finding max or min value
• Thinking it counts nodes instead of finding pairs
• Assuming it checks tree balance

2. Which of the following C# method signatures is correct for a function that checks if two nodes in a BST sum to a target value?

easy

A. string FindTarget(TreeNode root, int target)

B. bool FindTarget(TreeNode root, int target)

C. void FindTarget(TreeNode root, int target)

D. int FindTarget(TreeNode root, int target)

Solution

1. Step 1: Understand the expected return type

   The function should return true or false depending on whether two nodes sum to the target, so return type must be bool.

2. Step 2: Check method signature options

   bool FindTarget(TreeNode root, int target) returns bool, matching the requirement. Others return int, void, or string, which are incorrect for this purpose.

3. Final Answer:

   bool FindTarget(TreeNode root, int target) -> Option B

4. Quick Check:

   Return type bool for true/false check [OK]

Hint: Function returns true/false, so use bool return type [OK]

Common Mistakes:

• Using void return type and expecting a result
• Returning int or string instead of bool
• Incorrect parameter types

3. Given the BST below and target = 9, what will the function FindTarget return?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. runtime error

B. false

C. null

D. true

Solution

1. Step 1: Identify pairs that sum to target 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All these pairs exist in the BST.

2. Step 2: Confirm function behavior

   Since at least one pair (e.g., 2 and 7) sums to 9, the function should return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Pair exists with sum 9 = true [OK]

Hint: Check all node pairs for target sum quickly [OK]

Common Mistakes:

• Ignoring valid pairs in BST
• Assuming no pair without checking all nodes
• Confusing output with null or error

4. Consider this buggy code snippet for FindTarget in a BST:

public bool FindTarget(TreeNode root, int k) {
    HashSet<int> set = new HashSet<int>();
    return DFS(root, k, set);
}

private bool DFS(TreeNode node, int k, HashSet<int> set) {
    if (node == null) return false;
    if (set.Contains(k - node.val)) return true;
    set.Add(node.val);
    DFS(node.left, k, set);
    DFS(node.right, k, set);
    return false;
}

What is the main bug causing incorrect results?

medium

A. The base case should return true instead of false.

B. HashSet is not initialized properly.

C. DFS calls do not return their results, so always returns false.

D. The function should use a queue instead of recursion.

Solution

1. Step 1: Analyze DFS recursive calls

   The DFS calls to left and right subtrees are made but their return values are ignored.

2. Step 2: Understand impact on return value

   Because the recursive calls' results are not returned or checked, the function always returns false unless the first node matches.

3. Step 3: Correct fix

   Return the result of DFS calls combined with OR logic to propagate true upwards.

4. Final Answer:

   DFS calls do not return their results, so always returns false. -> Option C

5. Quick Check:

   Missing return in recursion causes false always [OK]

Hint: Always return recursive call results in DFS [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Incorrect base case return value
• Unnecessary data structure misuse

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? A) Convert BST to sorted list using inorder traversal, then use two pointers to find the sum. B) Use a HashSet during DFS to check complements without extra traversal. C) Check every pair of nodes by traversing the BST twice. D) Insert all node values into a queue and check sums by dequeuing pairs.

hard

A. Use HashSet during DFS to check complements.

B. Convert BST to sorted list and use two pointers.

C. Check every pair by traversing BST twice.

D. Use a queue to check sums by dequeuing pairs.

Solution

1. Step 1: Analyze each approach's efficiency

   Approach A uses O(n) space and O(n) time for traversal plus O(n) for two pointers. Approach B uses O(n) space but only one traversal with O(n) time. Approach C is O(n^2) time, inefficient. Approach D is unclear and inefficient.

2. Step 2: Choose the most efficient method

   Using a HashSet during DFS (Approach B) is efficient in time and space, as it checks complements on the fly without extra traversal.

3. Final Answer:

   Use HashSet during DFS to check complements. -> Option A

4. Quick Check:

   HashSet during DFS = efficient O(n) time and space [OK]

Hint: Use HashSet in one DFS pass for best efficiency [OK]

Common Mistakes:

• Choosing double traversal with two pointers over HashSet
• Trying all pairs causing O(n^2) time
• Using queues unnecessarily increasing complexity