5.19 Two Sum IV - Input is a BST

5.19.1 Problem Metadata

5.19.2 Description

Given the root of a Binary Search Tree and an integer k, return true if there exist two distinct nodes whose values sum to k. Otherwise, return false.

5.19.3 Examples

BST used in the example.

Figure 5.4: BST used in the example. 

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Explanation: 2 + 7 = 9.

5.19.4 Constraints

  • 1 <= nodes <= 10^4
  • -10^4 <= Node.val <= 10^4
  • BST property holds for the entire tree

5.19.5 Solution - DFS + HashSet

5.19.5.1 Walkthrough

Traverse the tree with DFS while maintaining a set of seen node values. For each node:

  1. Compute needed = k - node.val.
  2. If needed is already in the set, return true.
  3. Otherwise, insert node.val and continue exploring the left and right subtrees.

Because every value is checked exactly once, the traversal stays linear.

5.19.5.2 Analysis

  • Time Complexity: O(n) - Visit each node exactly once
  • Space Complexity: O(n) - HashSet stores up to n values + O(h) recursion stack where h is tree height

Why Not Use BST Property? While we could use in-order traversal to get sorted values and then apply two pointers, the DFS + HashSet approach is simpler and has the same O(n) time complexity.

BST-Specific Optimization: Could implement bidirectional BST iterator (one forward, one backward) for O(h) space instead of O(n), but added complexity rarely justifies the space savings.

Trade-off: We sacrifice O(n) space for code simplicity. The BST property doesn’t provide significant advantage over treating it as a general binary tree for this problem.

5.19.5.3 Implementation Steps

  1. Initialize an empty HashSet<Integer>.
  2. Perform DFS:
    1. If the node is null, return false.
    2. If set contains k - node.val, return true.
    3. Add node.val to the set.
    4. Recurse into left or right subtrees; return true if either side finds a match.
  3. Return false if no pair exists.

5.19.5.4 Code - Java

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

private boolean dfs(TreeNode node, int target, Set<Integer> seen) {
    if (node == null) {
        return false;
    }

    int needed = target - node.val;
    if (seen.contains(needed)) {
        return true;
    }

    seen.add(node.val);
    return dfs(node.left, target, seen) || dfs(node.right, target, seen);
}