How do you solve Two Sum IV - Input is a BST on LeetCode?

Two Sum IV - Input is a BST (LeetCode #653) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashSet allows for O(1) average-time complexity lookups.

What is the brute force solution for Two Sum IV - Input is a BST?

The brute force approach for Two Sum IV - Input is a BST is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every pair of nodes in the BST to see if their values sum to k. This is straightforward but inefficient, especially for larger trees. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Two Sum IV - Input is a BST?

Explain your thought process clearly; interviewers value understanding. Consider edge cases, like very small trees or negative values. Practice writing clean, efficient code under time constraints.

What are common mistakes when solving Two Sum IV - Input is a BST?

Not considering the case where the same node can be counted twice. Overlooking the need to check for complements in the HashSet.

#653

Two Sum IV - Input is a BST

Easy

Hash TableTwo PointersTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary TreeHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a HashSet allows us to efficiently check for the complement of each node's value as we traverse the BST. This reduces the time complexity significantly.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty HashSet to store the values we have seen.
2Step 2: Perform a depth-first traversal of the BST.
3Step 3: For each node, calculate the complement (k - node.val). If the complement is already in the HashSet, return true.
4Step 4: Otherwise, add the current node's value to the HashSet and continue the traversal.
5Step 5: If the traversal completes without finding a pair, return false.

solution.py19 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def findTarget(self, root: TreeNode, k: int) -> bool:
10        seen = set()
11        return self.dfs(root, k, seen)
12
13    def dfs(self, node, k, seen):
14        if not node:
15            return False
16        if (k - node.val) in seen:
17            return True
18        seen.add(node.val)
19        return self.dfs(node.left, k, seen) or self.dfs(node.right, k, seen)

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(n) due to the HashSet storing up to n values in the worst case.

1Using a HashSet allows for O(1) average-time complexity lookups.
2In-order traversal gives sorted values, but we can optimize with a HashSet.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.