Two Sum in BST in DSA Java - 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, checking pairs in a tree would be slow and complicated, making many applications like searching or matching data less efficient.

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 smartly searching from smallest and largest values simultaneously.

Think of it like...

It's like two people starting at opposite ends of a sorted list of prices, moving inward to find two items that together cost exactly what you want to spend.

BST Inorder Traversal (sorted):
[ 2, 3, 5, 7, 9, 12 ]

Two pointers:
  left -> points to smallest (2)
  right -> points to largest (12)

Check sum = 2 + 12 = 14
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 Tree Basics

Concept: Learn what a BST is and how its structure helps in searching.

A Binary Search Tree is a tree where each node has up to two children. The left child is smaller than the node, and the right child is bigger. This property means if you do an inorder traversal (left, node, right), you get a sorted list of values.

Result

You can get a sorted list of all values in the BST by inorder traversal.

Understanding BST structure is key because it allows us to use sorted order properties to find pairs efficiently.

2

Foundation

Inorder Traversal to Get Sorted Values

Concept: Use inorder traversal to convert BST nodes into a sorted list.

Inorder traversal visits nodes in ascending order. For example, for BST with nodes 5, 3, 7, 2, 9, 12, the inorder traversal output is [2, 3, 5, 7, 9, 12]. This sorted list is easier to work with for sum problems.

Result

Sorted list of BST values: [2, 3, 5, 7, 9, 12]

Converting BST to a sorted list simplifies the problem to a classic two-sum in an array.

3

Intermediate

Two Pointer Technique on Sorted Array

🤔Before reading on: do you think starting both pointers at the ends or the middle is better to find two numbers summing to target? Commit to your answer.

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

Set one pointer at the start (smallest value) and one at the end (largest value). Calculate their sum. If sum equals target, return true. If sum is less, move start pointer right to increase sum. If sum is more, move end pointer left to decrease sum. Repeat until pointers meet.

Result

Efficiently find if two numbers sum to target without checking all pairs.

Two pointers exploit sorted order to reduce time from checking all pairs (O(n^2)) to linear time (O(n)).

4

Intermediate

Applying Two Pointer Technique Directly on BST

🤔Before reading on: do you think we must convert BST to list first or can we do two pointers directly on BST? Commit to your answer.

Concept: Instead of converting BST to a list, use two iterators that traverse the BST in ascending and descending order to simulate two pointers.

Create two iterators: one does normal inorder traversal (smallest to largest), the other does reverse inorder traversal (largest to smallest). Each iterator gives the next smallest or largest value. Compare sums from these iterators like two pointers in an array.

Result

Find two sum in BST without extra space for full list, using O(h) space where h is tree height.

Using BST iterators directly saves memory and keeps the solution efficient for large trees.

5

Advanced

Implementing BST Iterators for Two Sum

🤔Before reading on: do you think BST iterators use recursion or stacks internally? Commit to your answer.

Concept: BST iterators use stacks to remember nodes during traversal, allowing controlled next smallest or largest retrieval.

For inorder iterator: push all left children starting from root to stack. Next() pops from stack, pushes right child's left children. For reverse iterator: push all right children similarly. This simulates moving pointers inward.

Result

Two iterators that can give next smallest and next largest values in O(1) average time per call.

Understanding stack-based iterators reveals how to traverse BST partially without full traversal or extra memory.

6

Expert

Handling Edge Cases and Performance in Two Sum BST

🤔Before reading on: do you think duplicate values in BST affect two sum logic? Commit to your answer.

Concept: Consider duplicates, single-node trees, and performance trade-offs in real-world BST two sum implementations.

Duplicates can be handled by ensuring iterators do not point to the same node twice. Single-node trees cannot have two sum. Performance depends on tree height; balanced trees give O(log n) space and time per iterator step, while skewed trees degrade to O(n).

Result

Robust two sum solution that works correctly and efficiently in all BST shapes and values.

Knowing edge cases prevents bugs and helps choose balanced BSTs or augment data structures for better performance.

Under the Hood

The two-pointer technique on BST uses two controlled traversals: one from smallest to largest (inorder) and one from largest to smallest (reverse inorder). Each traversal uses a stack to remember nodes not yet visited. By comparing values from these traversals, the algorithm moves pointers inward without storing all nodes, achieving O(h) space where h is tree height.

Why designed this way?

This approach avoids converting the BST to a full sorted list, saving memory. It leverages BST properties and stack-based traversal to efficiently find pairs summing to target. Alternatives like full list conversion use more space, and naive pair checking is too slow.

BST Two Sum Mechanism:

  [BST Root]
     /    \
 [Left]  [Right]
   |        |
Stack L   Stack R
   |        |
Inorder  Reverse Inorder
   |        |
  Next L   Next R
     \      /
      Compare sum
       /      \
  sum < target  sum > target
     |            |
 Move L right  Move R left

Repeat until L meets R or sum found

Myth Busters - 3 Common Misconceptions

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

Common Belief: Converting the BST to a sorted list is the simplest and best way to solve two sum.

Reality: While converting to a list works, it uses extra memory proportional to the number of nodes, which can be large. Using two BST iterators is more memory efficient.

Why it matters: Using extra memory can cause performance issues or crashes in large trees or memory-limited environments.

Quick: Do you think two sum in BST can be solved by just checking each node against all others? Commit yes or no.

Common Belief: Checking every pair of nodes is a straightforward way to find two sum in BST.

Reality: This approach is very slow (O(n^2)) and inefficient for large trees. Using BST properties and two pointers reduces time to O(n).

Why it matters: Inefficient solutions cause slow programs and poor user experience in real applications.

Quick: Do you think the two pointers can point to the same node to form the sum? Commit yes or no.

Common Belief: The two pointers can point to the same node if its value times two equals the target.

Reality: Two sum requires two distinct nodes. Using the same node twice is not allowed, even if its value times two equals the target.

Why it matters: Allowing the same node twice leads to incorrect results and bugs.

Expert Zone

1

BST iterators rely on controlled stack usage to simulate pointer movement without full traversal, which is subtle but powerful.

2

Handling duplicates requires careful iterator advancement to avoid counting the same node twice.

3

The approach's efficiency depends heavily on tree balance; skewed trees degrade performance and space.

When NOT to use

Avoid this approach if the BST is extremely unbalanced or if you need to find all pairs, not just one. For all pairs, consider hashing or flattening the tree. For unbalanced trees, balancing or using balanced BST variants is better.

Production Patterns

In production, this pattern is used in database indexing, where BST-like structures (B-trees) help find matching pairs efficiently. Also used in memory-constrained systems where full list conversion is too costly.

Connections

Two Sum in Sorted Array

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

Understanding two pointers in arrays helps grasp how BST iterators simulate the same logic without extra space.

Inorder and Reverse Inorder Traversal

Two Sum in BST uses these two traversal methods simultaneously.

Knowing these traversals deeply helps implement efficient BST iterators for many problems beyond two sum.

Database Indexing

BST structures and two-pointer search relate to how databases quickly find matching records.

Recognizing this connection shows how fundamental BST two sum logic is to real-world data retrieval systems.

Common Pitfalls

#1 Using full BST traversal to list without considering memory limits.

Wrong approach:

List values = new ArrayList<>();
void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
values.add(node.val);
inorder(node.right);
}
// then two pointers on values list

Correct approach:

Use two BST iterators with stacks to simulate two pointers without full list conversion.

Root cause:

Assuming memory is unlimited and ignoring large tree constraints.

#2 Allowing two pointers to point to the same node for sum.

Wrong approach:

if (leftVal + rightVal == target) return true; // without checking if pointers differ

Correct approach:

Ensure iterators do not cross or point to the same node before returning true.

Root cause:

Misunderstanding that two sum requires distinct elements.

#3 Using recursion for BST iterators leading to stack overflow on large trees.

Wrong approach:

Recursive inorder traversal with no stack control for iterator next calls.

Correct approach:

Use explicit stack-based iterators to control traversal and avoid deep recursion.

Root cause:

Not considering recursion depth limits and iterator design.

Key Takeaways

Two Sum in BST finds if two distinct nodes sum to a target using BST properties and efficient traversal.

Inorder and reverse inorder traversals simulate two pointers moving inward from smallest and largest values.

Stack-based BST iterators avoid full list conversion, saving memory and improving performance.

Handling edge cases like duplicates and tree shape is crucial for correct and efficient solutions.

This problem connects fundamental BST traversal techniques to practical applications like database indexing.

Practice

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

easy

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

B. Find the maximum value in the BST.

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

D. Check if the BST is balanced.

Solution

1. Step 1: Understand the problem statement

   The problem asks to find if there exist two nodes in the BST such that their values add up to a given target.

2. Step 2: Identify the goal

   The goal is to check for the existence of such a pair, not to find max, balance, or count nodes.

3. Final Answer:

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

4. Quick Check:

   Two Sum in BST means finding two nodes summing to target [OK]

Hint: Remember Two Sum means pair sums to target [OK]

Common Mistakes:

• Confusing Two Sum with finding max value
• Thinking problem is about BST balance
• Counting nodes instead of finding pairs

2. Which of the following Java method signatures correctly represents a function to solve Two Sum in BST?

easy

A. public int findSum(TreeNode root, int k)

B. public boolean findTarget(TreeNode root, int k)

C. public void findTarget(TreeNode root, int k)

D. public TreeNode findPair(TreeNode root, int k)

Solution

1. Step 1: Understand the return type needed

   The function should return true or false if a pair exists, so return type is boolean.

2. Step 2: Check method signatures

   public boolean findTarget(TreeNode root, int k) returns boolean and accepts root and target, matching the problem requirements.

3. Final Answer:

   public boolean findTarget(TreeNode root, int k) -> Option B

4. Quick Check:

   Boolean return for existence check [OK]

Hint: Two Sum returns true/false, so use boolean return [OK]

Common Mistakes:

• Using void return type instead of boolean
• Returning int instead of boolean
• Returning TreeNode instead of boolean

3. Given the BST below and target = 9, what will the output of findTarget(root, 9) be?

      5
     / \
    3   6
   / \   \
  2   4   7

medium

A. true

B. false

C. null

D. Runtime Error

Solution

1. Step 1: Identify pairs that sum to 9

   Check pairs: 2+7=9, 3+6=9, 4+5=9. All valid pairs exist.

2. Step 2: Confirm function returns true if any pair found

   Since pairs exist, function returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Pairs 2+7 or 3+6 sum to 9 [OK]

Hint: Check pairs adding to target in BST nodes [OK]

Common Mistakes:

• Ignoring valid pairs and returning false
• Confusing output with node values
• Assuming null or error without reason

4. Consider this buggy code snippet for Two Sum in BST:

public boolean findTarget(TreeNode root, int k) {
    Set<Integer> set = new HashSet<>();
    return dfs(root, k, set);
}

private boolean dfs(TreeNode node, int k, Set<Integer> 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. Using HashSet instead of ArrayList.

B. Adding node values after checking set.

C. Not checking if root is null in findTarget.

D. Missing return statements from recursive calls in dfs.

Solution

1. Step 1: Analyze dfs recursive calls

   dfs calls itself on left and right but ignores their return values.

2. Step 2: Understand impact of missing returns

   Without returning results of recursive calls, function always returns false unless first node matches.

3. Step 3: Correct fix

   Return true if either left or right dfs call returns true.

4. Final Answer:

   Missing return statements from recursive calls in dfs. -> Option D

5. Quick Check:

   Return recursive calls to propagate true [OK]

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

Common Mistakes:

• Ignoring return values of recursive calls
• Using wrong data structure for lookup
• Not handling null root properly

5. You want to optimize Two Sum in BST to use O(h) space, where h is tree height. Which approach is best?

hard

A. Use two iterators: one in-order and one reverse in-order traversal.

B. Store all node values in a list and use two pointers.

C. Use a HashSet to store visited nodes during DFS.

D. Convert BST to sorted array and binary search for complements.

Solution

1. Step 1: Understand space complexity of approaches

   Storing all nodes uses O(n) space; HashSet also O(n); array conversion O(n).

2. Step 2: Two iterator approach

   Using two iterators (in-order and reverse in-order) simulates two pointers with O(h) space.

3. Step 3: Choose best approach

   Use two iterators: one in-order and one reverse in-order traversal. uses O(h) space and is optimal for BST Two Sum.

4. Final Answer:

   Use two iterators: one in-order and one reverse in-order traversal. -> Option A

5. Quick Check:

   Two iterators give O(h) space [OK]

Hint: Two pointers in BST use two iterators for O(h) space [OK]

Common Mistakes:

• Using full list storage causing O(n) space
• Relying on HashSet which uses O(n) space
• Ignoring BST properties for optimization