Domain 1EasyCORE

Two Sum IV - Input is a BST

The problem asks us to determine if there are two distinct nodes in a Binary Search Tree (BST) such that their values sum up to a given target number `k`. The inputs are the root of the BST and the target integer `k`. The output is a boolean value: `true` if such a pair exists, and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

653. Two Sum IV - Input is a BST

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 0
Acceptance rate: 56.4%


Problem Breakdown

The problem asks us to determine if there are two distinct nodes in a Binary Search Tree (BST) such that their values sum up to a given target number k. The inputs are the root of the BST and the target integer k. The output is a boolean value: true if such a pair exists, and false otherwise.

Implicit constraints include:

  • The tree can have between 1 and 10^4 nodes.
  • Node values range from -10^4 to 10^4.
  • The target k ranges from -10^5 to 10^5.

Edge cases might include:

  • A single-node tree.
  • All nodes having the same value.
  • Negative node values and target.

Intuition

A brute-force approach would involve checking every pair of nodes in the tree, which would result in a time complexity of O(n^2), where n is the number of nodes. This is inefficient for large trees.

The key insight is to leverage the properties of a BST and use a set to track seen values. As we traverse the tree, we can check if the complement (i.e., k - current_node.val) exists in the set. If it does, we have found our pair. This approach reduces the time complexity to O(n) by ensuring each node is visited only once.

Approach

  1. Initialize an empty set to keep track of seen values.
  2. Perform a depth-first search (DFS) traversal on the BST.
  3. For each node:
    • Calculate its complement with respect to k.
    • Check if this complement exists in the set.
    • If it does, return true.
    • Otherwise, add the current node’s value to the set and continue the traversal.
  4. If the traversal completes without finding a pair, return false.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  • Space Complexity: O(n) in the worst case, where all node values are stored in the set.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findTarget(root: 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)

Edge Cases Handled

  • Single-node tree: The algorithm will correctly return false since there is no other node to pair with.
  • All nodes having the same value: If k is twice the node value and there are at least two nodes, it will return true.
  • Negative node values and target: The set-based approach naturally handles negative numbers without any special cases.