Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Two Sum IV - Input is a BST

EASYProblemSolveExternal Links

Description

You are given the root of a Binary Search Tree (BST) and an integer k. Your task is to determine whether there exist two distinct nodes in the BST whose values add up to exactly k.

A BST is a binary tree where for every node, all values in its left subtree are strictly smaller, and all values in its right subtree are strictly larger. You need to return true if any pair of different nodes sums to k, and false otherwise.

Examples

Example 1

Input: root = [5,3,6,2,4,null,7], k = 9

Output: true

Explanation: The BST has the following structure:

       5
      / \
     3   6
    / \   \
   2   4   7

We can find the pair of nodes with values 2 and 7: 2 + 7 = 9 = k. Another valid pair is nodes 4 and 5: 4 + 5 = 9 = k. Since at least one valid pair exists, the answer is true.

Example 2

Input: root = [5,3,6,2,4,null,7], k = 28

Output: false

Explanation: Using the same BST, no pair of node values sums to 28. The two largest values in the tree are 6 and 7, and their sum is only 13. Since every possible pair produces a sum far below 28, the answer is false.

Constraints

  • 1 ≤ Number of nodes ≤ 10^4
  • -10^4 ≤ Node.val ≤ 10^4
  • root is guaranteed to be a valid Binary Search Tree
  • -10^5 ≤ k ≤ 10^5

Editorial

Brute Force

Intuition

The simplest way to check if two node values in the BST sum to k is to first collect every value from the tree, then examine all possible pairs.

Imagine emptying a jar of numbered marbles onto a table. You pick up the first marble and compare its number with every other marble, checking if the two numbers add up to your target. If no pair works with the first marble, you set it aside, pick up the second, and repeat the process.

To implement this, we first traverse the entire BST using DFS and store every node's value in a list. Then we use two nested loops: the outer loop picks one value, and the inner loop tries every subsequent value to see if the pair sums to k.

Step-by-Step Explanation

Let's trace through Example 1 with root = [5,3,6,2,4,null,7] and k = 9:

Step 1: Traverse the BST using pre-order DFS and collect all values into a list: [5, 3, 2, 4, 6, 7].

Step 2: Fix i = 0 (value 5). We need to find another value that sums with 5 to make 9, so we are looking for 4.

Step 3: Check pair (i=0, j=1): values[0] + values[1] = 5 + 3 = 8. Is 8 equal to 9? No. Move to the next j.

Step 4: Check pair (i=0, j=2): values[0] + values[2] = 5 + 2 = 7. Is 7 equal to 9? No. Move to the next j.

Step 5: Check pair (i=0, j=3): values[0] + values[3] = 5 + 4 = 9. Is 9 equal to 9? YES!

Step 6: Return true. The pair (5, 4) sums to k = 9. We found the answer after checking only 3 pairs.

Brute Force — Checking All Pairs — Watch how we collect all BST values into an array, then systematically check every pair until we find two values summing to k.

Algorithm

  1. Traverse the BST using DFS and collect all node values into a list
  2. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • If values[i] + values[j] == k, return true
  3. If no pair found after checking all combinations, return false

Code

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> values;
        collect(root, values);
        int n = values.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (values[i] + values[j] == k) {
                    return true;
                }
            }
        }
        return false;
    }

    void collect(TreeNode* node, vector<int>& values) {
        if (!node) return;
        values.push_back(node->val);
        collect(node->left, values);
        collect(node->right, values);
    }
};
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        values = []

        def collect(node):
            if not node:
                return
            values.append(node.val)
            collect(node.left)
            collect(node.right)

        collect(root)

        n = len(values)
        for i in range(n):
            for j in range(i + 1, n):
                if values[i] + values[j] == k:
                    return True
        return False
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        collect(root, values);
        int n = values.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (values.get(i) + values.get(j) == k) {
                    return true;
                }
            }
        }
        return false;
    }

    private void collect(TreeNode node, List<Integer> values) {
        if (node == null) return;
        values.add(node.val);
        collect(node.left, values);
        collect(node.right, values);
    }
}

Complexity Analysis

Time Complexity: O(n²)

Collecting all node values requires a single DFS traversal, taking O(n). The nested loops then check n × (n-1) / 2 pairs, which is O(n²). The pair-checking dominates, giving O(n²) overall.

Space Complexity: O(n)

We store all n node values in a list. The DFS recursion stack uses O(h) space where h is the tree height, but the list of values dominates at O(n).

Why This Approach Is Not Efficient

The brute force examines all O(n²) pairs of values. With n up to 10^4, that means up to approximately 5 × 10^7 pair comparisons in the worst case — pushing against typical time limits for competitive programming judges.

The core issue is that for each value, we perform a linear scan of the remaining values to find its complement. We do not remember what we have already seen. If we could check whether a specific value exists in constant time O(1) instead of scanning through O(n) values, we would reduce the total time from O(n²) to O(n).

A hash set provides exactly this O(1) membership check. Instead of collecting values into a plain list and checking all pairs afterward, we can check for the complement on the fly as we traverse the tree.

Better Approach - DFS with Hash Set

Intuition

Instead of collecting all values first and then checking pairs, we can check for the complement on the fly during a single tree traversal. For each node we visit, we ask one question: "Have I already seen a node whose value equals k minus my value?" If the answer is yes, we have found our pair. If not, we record our value in a hash set and move on.

Imagine walking through a group of people at a party, each wearing a name tag with a number. You carry a notebook listing every person you have already met. When you meet someone new with number x, you flip through your notebook looking for the number k - x. If it is there, you have found your pair instantly. If not, you write x in your notebook and continue to the next person.

This approach works on any binary tree — it does not require the BST property at all. The hash set gives O(1) lookup, turning the problem into a single-pass O(n) solution.

Step-by-Step Explanation

Let's trace through Example 1 with root = [5,3,6,2,4,null,7] and k = 9:

Step 1: Initialize an empty hash set. Start DFS from the root node.

Step 2: Visit root (value 5). Complement = 9 - 5 = 4. Is 4 in the set? No (set is empty). Add 5 to the set. Set = {5}.

Step 3: Move to left child. Visit node 3. Complement = 9 - 3 = 6. Is 6 in the set {5}? No. Add 3 to the set. Set = {5, 3}.

Step 4: Move to left child of 3. Visit node 2. Complement = 9 - 2 = 7. Is 7 in the set {5, 3}? No. Add 2 to the set. Set = {5, 3, 2}.

Step 5: Node 2 has no children. Backtrack to node 3. Move to right child of 3. Visit node 4. Complement = 9 - 4 = 5. Is 5 in the set {5, 3, 2}? YES!

Step 6: Match found! Node 4 (value 4) and a previously visited node (value 5) sum to 9. Return true.

DFS with Hash Set — Finding Complement During Traversal — Watch how we traverse the BST with DFS while maintaining a hash set of visited values, checking for the complement at each node before adding the current value.

Algorithm

  1. Create an empty hash set to store visited node values
  2. Perform DFS starting from the root
  3. At each node:
    • Compute complement = k - node.val
    • If complement exists in the set, return true
    • Otherwise, add node.val to the set
    • Recursively check left subtree, then right subtree
  4. If DFS completes without finding a pair, return false

Code

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> seen;
        return dfs(root, k, seen);
    }

    bool dfs(TreeNode* node, int k, unordered_set<int>& seen) {
        if (!node) return false;
        if (seen.count(k - node->val)) return true;
        seen.insert(node->val);
        return dfs(node->left, k, seen) || dfs(node->right, k, seen);
    }
};
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()

        def dfs(node):
            if not node:
                return False
            complement = k - node.val
            if complement in seen:
                return True
            seen.add(node.val)
            return dfs(node.left) or dfs(node.right)

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

    private boolean dfs(TreeNode node, int k, Set<Integer> seen) {
        if (node == null) return false;
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left, k, seen) || dfs(node.right, k, seen);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once during the DFS traversal. At each node, the hash set lookup (complement in seen) and insertion (seen.add) are both O(1) on average. Total: n nodes × O(1) work per node = O(n).

Space Complexity: O(n)

The hash set can store up to n values in the worst case (when no pair is found until the very end or no pair exists). The DFS recursion stack uses O(h) space where h is the tree height — O(log n) for a balanced BST, O(n) for a completely skewed tree. The hash set dominates, giving O(n) overall.

Why This Approach Is Not Efficient

The DFS with hash set achieves O(n) time, which is optimal since we must examine each node at least once. However, it uses O(n) extra space for the hash set and completely ignores the BST property.

A Binary Search Tree has a powerful structural advantage: its inorder traversal (left → root → right) produces values in sorted ascending order. This is a gift we are not using. If we extract this sorted sequence, we can apply the classic two-pointer technique — placing one pointer at the smallest value and another at the largest, then narrowing the search window based on whether the current sum is too small or too large.

While this approach also uses O(n) space to store the sorted array, it demonstrates an important problem-solving pattern: converting a tree problem into a well-known sorted array problem by leveraging the BST's ordering guarantee. This pattern appears frequently in BST problems and is a valuable technique to master.

Optimal Approach - Inorder Traversal + Two Pointers

Intuition

A BST has a remarkable property: if you perform an inorder traversal (visit left subtree, then root, then right subtree), you get all the values in sorted ascending order. For our tree with nodes [5, 3, 6, 2, 4, 7], the inorder traversal produces [2, 3, 4, 5, 6, 7] — perfectly sorted without any extra sorting step.

Once we have a sorted array, finding two numbers that sum to a target is a classic two-pointer problem. Place one pointer at the start (smallest value) and another at the end (largest value):

  • If the sum of the two pointed values is less than k, the left element is too small — move the left pointer rightward to increase the sum.
  • If the sum is greater than k, the right element is too large — move the right pointer leftward to decrease the sum.
  • If the sum equals k, we have found our pair.

This approach transforms a tree problem into a sorted-array two-pointer problem, using the BST property as a bridge between the two.

BST with inorder traversal arrows showing how the sorted sequence [2, 3, 4, 5, 6, 7] is extracted
BST with inorder traversal arrows showing how the sorted sequence [2, 3, 4, 5, 6, 7] is extracted

Step-by-Step Explanation

Let's trace through Example 1 with root = [5,3,6,2,4,null,7] and k = 9:

Step 1: Perform inorder traversal of the BST. Starting from the root, go left repeatedly until reaching the leftmost node (2). Then visit 3, its right child 4, back to root 5, then the right subtree: 6 and 7. The resulting sorted array is [2, 3, 4, 5, 6, 7].

Step 2: Initialize two pointers: left at index 0 pointing to value 2 (the smallest element), and right at index 5 pointing to value 7 (the largest element).

Step 3: Compute sum = arr[left] + arr[right] = 2 + 7 = 9.

Step 4: Compare sum with target: 9 == 9? YES! The sum equals k.

Step 5: Return true. The pair (2, 7) sums to 9.

Note: In this example, we found the pair immediately. In general, if the sum were less than k, we would move the left pointer right (increasing the smaller value). If the sum were greater than k, we would move the right pointer left (decreasing the larger value). This narrowing continues until either a pair is found or the pointers cross.

Inorder + Two Pointers — Sorted Array Search — Watch how the BST is flattened into a sorted array via inorder traversal, then two pointers converge from both ends to find a pair summing to k.

Algorithm

  1. Perform an inorder traversal of the BST to collect all values into a sorted array
  2. Initialize two pointers: left = 0, right = array.length - 1
  3. While left < right:
    • Compute sum = arr[left] + arr[right]
    • If sum == k, return true
    • If sum < k, increment left (move toward larger values)
    • If sum > k, decrement right (move toward smaller values)
  4. If pointers cross without finding a pair, return false

Code

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        vector<int> sorted;
        inorder(root, sorted);
        int left = 0, right = sorted.size() - 1;
        while (left < right) {
            int sum = sorted[left] + sorted[right];
            if (sum == k) return true;
            else if (sum < k) left++;
            else right--;
        }
        return false;
    }

    void inorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
    }
};
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        sorted_vals = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            sorted_vals.append(node.val)
            inorder(node.right)

        inorder(root)

        left, right = 0, len(sorted_vals) - 1
        while left < right:
            current_sum = sorted_vals[left] + sorted_vals[right]
            if current_sum == k:
                return True
            elif current_sum < k:
                left += 1
            else:
                right -= 1

        return False
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> sorted = new ArrayList<>();
        inorder(root, sorted);
        int left = 0, right = sorted.size() - 1;
        while (left < right) {
            int sum = sorted.get(left) + sorted.get(right);
            if (sum == k) return true;
            else if (sum < k) left++;
            else right--;
        }
        return false;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits each of the n nodes exactly once, taking O(n) time. The two-pointer scan traverses the sorted array at most once — each step either moves the left pointer forward or the right pointer backward, and they can meet in at most n steps. Total: O(n) + O(n) = O(n).

Space Complexity: O(n)

We store all n node values in the sorted array. The inorder traversal's recursion stack uses O(h) additional space where h is the tree height. The array dominates at O(n).

Note: Both this approach and the hash set approach are O(n) time and O(n) space. The key advantage of this approach is that it leverages the BST property (sorted inorder) and uses the well-known two-pointer pattern. For a follow-up optimization, one could use BST iterators (one forward, one reverse) to achieve O(h) space without materializing the entire sorted array.