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
kranges 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
- Initialize an empty set to keep track of seen values.
- Perform a depth-first search (DFS) traversal on the BST.
- 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.
- Calculate its complement with respect to
- 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
falsesince there is no other node to pair with. - All nodes having the same value: If
kis twice the node value and there are at least two nodes, it will returntrue. - Negative node values and target: The set-based approach naturally handles negative numbers without any special cases.