Two Sum IV - Input is a BST — DSA · Engineering Playbook

Problem#

Given the root of a BST and an integer k, return whether any pair of distinct node values sums to k.

Examples#

root [5,3,6,2,4,null,7], k = 9 → true (2 + 7).
root [5,3,6,2,4,null,7], k = 28 → false.

Constraints#

1 <= n <= 10^4, -10^4 <= Node.val <= 10^4, -10^5 <= k <= 10^5.

Hints#

Hint

Treat it like Two Sum: traverse once, for each value look up k - val in a set.

Approach#

Any traversal works; the BST property is a red herring for the hash-set solution. For each visited node, return true if k - node->val has been seen; otherwise insert node->val.

Solution#

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

func findTarget(root *TreeNode, k int) bool {
  seen := map[int]bool{}
  var dfs func(n *TreeNode) bool
  dfs = func(n *TreeNode) bool {
    if n == nil {
      return false
    }
    if seen[k-n.Val] {
      return true
    }
    seen[n.Val] = true
    return dfs(n.Left) || dfs(n.Right)
  }
  return dfs(root)
}

from typing import Optional

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen: set[int] = set()

        def dfs(n: Optional[TreeNode]) -> bool:
            if n is None:
                return False
            if k - n.val in seen:
                return True
            seen.add(n.val)
            return dfs(n.left) or dfs(n.right)

        return dfs(root)

var findTarget = function(root, k) {
    const seen = new Set();
    const dfs = (n) => {
        if (!n) return false;
        if (seen.has(k - n.val)) return true;
        seen.add(n.val);
        return dfs(n.left) || dfs(n.right);
    };
    return dfs(root);
};

class Solution {
    private Set<Integer> seen = new HashSet<>();

    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        if (seen.contains(k - root.val)) return true;
        seen.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}

function findTarget(root: TreeNode | null, k: number): boolean {
    const seen = new Set<number>();
    const dfs = (n: TreeNode | null): boolean => {
        if (!n) return false;
        if (seen.has(k - n.val)) return true;
        seen.add(n.val);
        return dfs(n.left) || dfs(n.right);
    };
    return dfs(root);
}

Editorial#

The BST shape makes an alternative O(n) / O(h) approach available: inorder traversal yields sorted values, then a two-pointer scan checks pairs. The hash-set version is simpler and runs in the same big-O time with O(n) space.

Complexity#

Time: O(n).
Space: O(n) for the set (and recursion stack).

Concept revision#

Two Sum

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#