Two Sum in BST in DSA Java - Build from Scratch

Two Sum in BST

📖 Scenario: You are working on a simple banking system that stores customer account balances in a Binary Search Tree (BST). You want to find if there are two accounts whose balances add up to a specific target amount. This helps in quickly identifying pairs of accounts for special offers or fraud detection.

🎯 Goal: Build a Java program that creates a BST with given account balances, sets a target sum, and checks if there exist two nodes in the BST whose values add up to the target sum.

📋 What You'll Learn

Create a BST by inserting given integer values representing account balances.

Create a variable to hold the target sum value.

Implement a method to check if there exist two nodes in the BST whose sum equals the target.

Print true if such a pair exists, otherwise false.

💡 Why This Matters

🌍 Real World

Finding pairs of values that sum to a target is useful in fraud detection, recommendation systems, and financial analysis where data is stored in sorted structures like BSTs.

💼 Career

This project teaches tree traversal, hashing, and problem-solving skills commonly asked in software engineering interviews and used in backend data processing.

1

Create the BST with given account balances

Create a class TreeNode with an integer val and two child nodes left and right. Then create a class BST with a method insert to add nodes. In the main method, create a BST and insert these exact values in order: 10, 5, 15, 3, 7, 18.

DSA Java

// Define TreeNode class
// Define BST class with insert method
// In main, create BST and insert 10, 5, 15, 3, 7, 18
// Your code here

Hint

Start by defining the TreeNode class with value and child pointers. Then create the BST class with an insert method that adds nodes correctly. Finally, insert the given values in the main method.

2

Set the target sum value

In the main method, create an integer variable called target and set it to 22.

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else {
            root.right = insertRec(root.right, val);
        }
        return root;
    }
}

public class Main {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(3);
        bst.insert(7);
        bst.insert(18);
        // Create target variable
        // Your code here
    }
}

Hint

Simply declare an integer variable named target and assign it the value 22 inside the main method.

3

Implement method to check for two sum in BST

Add a method findTarget in the BST class that takes TreeNode root and int k as parameters and returns boolean. Use a helper method to traverse the BST and a HashSet<Integer> to check if the complement (k - node.val) exists. In the main method, call bst.findTarget(bst.root, target) and store the result in a boolean variable called result.

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

import java.util.HashSet;

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else {
            root.right = insertRec(root.right, val);
        }
        return root;
    }

    // Add findTarget method here
    // Your code here
}

public class Main {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(3);
        bst.insert(7);
        bst.insert(18);
        int target = 22;
        // Call findTarget and store result
        // Your code here
    }
}

Hint

Use a HashSet to store visited node values. Traverse the BST recursively. For each node, check if k - node.val is in the set. If yes, return true. Otherwise, add the node value to the set and continue.

4

Print the result

In the main method, print the boolean variable result to display if two nodes sum to the target.

DSA Java

import java.util.HashSet;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    TreeNode root;

    void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val  set = new HashSet();
        return find(root, k, set);
    }

    private boolean find(TreeNode node, int k, HashSet set) {
        if (node == null) {
            return false;
        }
        if (set.contains(k - node.val)) {
            return true;
        }
        set.add(node.val);
        return find(node.left, k, set) || find(node.right, k, set);
    }
}

public class Main {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(3);
        bst.insert(7);
        bst.insert(18);
        int target = 22;
        boolean result = bst.findTarget(bst.root, target);
        // Print the result
        // Your code here
    }
}

Hint

Use System.out.println(result); to print the boolean result.

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