Difficulty: 🟢 Easy
Topics: Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Solution

LeetCode 653, Two Sum IV - Input is a BST

Problem Understanding

This problem gives us the root of a Binary Search Tree (BST) and an integer k. We must determine whether there are two distinct nodes in the tree whose values add up to k.

The input is a BST, which means the tree satisfies the BST ordering property:

Every node in the left subtree has a smaller value than the current node.
Every node in the right subtree has a larger value than the current node.

Even though the tree is a BST, the problem does not require us to return the actual pair of numbers. We only need to return a boolean value:

true if such a pair exists
false otherwise

For example, consider the tree:

If k = 9, the pair (2, 7) exists, so the answer is true.

If k = 28, there are no two nodes whose sum equals 28, so the answer is false.

The constraints are important:

The tree can contain up to 10^4 nodes.
Node values can be negative.
The BST is guaranteed to be valid.

Since the tree can be fairly large, an inefficient quadratic solution may become too slow. We should aim for a solution close to linear time.

Several edge cases are important to consider:

A tree with only one node can never form a valid pair.
The valid pair may involve negative numbers.
The same node cannot be used twice.
The matching pair may appear in completely different branches of the tree.
Duplicate values are generally not present in standard BSTs, but our logic should still correctly ensure that two separate nodes are required.

Approaches

Brute Force Approach

The most straightforward approach is to collect all node values into a list using a tree traversal, then check every possible pair.

We can perform a DFS or BFS traversal to extract all values into an array. After that, we use two nested loops:

The outer loop selects the first number.
The inner loop selects the second number.
For every pair, we check whether their sum equals k.

This approach is correct because it explicitly tests every possible pair of nodes. If a valid pair exists, it will eventually be found.

However, this method is inefficient. With n nodes, there are approximately n² / 2 pairs to check. For 10^4 nodes, this becomes too expensive.

Optimal Approach

The key observation is that this problem is essentially the classic "Two Sum" problem applied to a tree.

In the standard Two Sum problem, we iterate through numbers while storing previously seen values in a hash set. For each current value x, we check whether k - x has already been seen.

The exact same idea works here.

We traverse the BST using DFS or BFS. During traversal:

For the current node value x
Compute target = k - x
Check whether target already exists in a hash set
If it does, we found two numbers whose sum is k
Otherwise, add x to the set and continue traversal

This reduces the time complexity from quadratic to linear because hash set lookups are approximately O(1).

Even though the input is a BST, we do not actually need BST-specific ordering properties for this solution. We simply traverse every node once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Store all values, then test every pair
Optimal	O(n)	O(n)	DFS traversal with hash set lookups

Algorithm Walkthrough

Optimal DFS + Hash Set Algorithm

Create an empty hash set called seen.

This set stores values we have already visited during traversal. Hash sets provide constant-time average lookup, which makes complement checks efficient. 2. Start a DFS traversal from the root.

We can use either recursion or an explicit stack. Recursive DFS is simple and natural for tree problems. 3. For the current node, compute the complement.

If the current node value is x, then the value we need is:

$\text{complement} = k - x$ 4. Check whether the complement already exists in the hash set.

If it does, then we previously visited another node whose value plus the current value equals k. We immediately return True. 5. Otherwise, add the current node value to the hash set.

This makes the current value available as a potential complement for future nodes. 6. Recursively traverse the left subtree.

If the left subtree returns True, propagate the result upward immediately. 7. Recursively traverse the right subtree.

If the right subtree returns True, propagate the result upward immediately. 8. If traversal completes without finding a valid pair, return False.

Why it works

The algorithm maintains an invariant:

Before processing a node, the hash set contains exactly the values of previously visited nodes.

For each node value x, we check whether k - x already exists among previously visited values. If it does, then two distinct nodes sum to k.

Since every node is visited exactly once, every possible pair is considered exactly once in complement form. Therefore, the algorithm correctly detects whether a valid pair exists.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, Set

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

        def dfs(node: Optional[TreeNode]) -> bool:
            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)

The implementation starts by creating a hash set named seen. This set stores all node values encountered during traversal.

The nested dfs function performs recursive depth-first traversal. The base case handles None nodes by returning False.

For each node, the code computes the complement k - node.val. If this complement already exists in the hash set, we immediately return True because a valid pair has been found.

If no match exists, the current node value is inserted into the set so future nodes can use it as a complement candidate.

Finally, the function recursively explores both subtrees. The use of logical or ensures early termination as soon as a valid pair is found.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)

    var dfs func(node *TreeNode) bool

    dfs = func(node *TreeNode) bool {
        if node == nil {
            return false
        }

        complement := k - node.Val

        if seen[complement] {
            return true
        }

        seen[node.Val] = true

        return dfs(node.Left) || dfs(node.Right)
    }

    return dfs(root)
}

The Go solution follows the same algorithmic structure as the Python version.

Instead of Python's set, Go uses map[int]bool to simulate a hash set.

Nil checks replace Python's None checks. Recursive DFS is implemented using a function variable declaration because Go requires recursive anonymous functions to be declared before assignment.

Integer overflow is not a concern here because the problem constraints are small compared to Go's integer range.

Worked Examples

Example 1

Input:
root = [5,3,6,2,4,null,7]
k = 9

Tree:

Traversal order using DFS:

Current Node	Complement Needed	Seen Set Before	Match Found?	Seen Set After
5	4	{}	No	{5}
3	6	{5}	No	{3,5}
2	7	{3,5}	No	{2,3,5}
4	5	{2,3,5}	Yes	return True

When visiting node 4, the complement needed is 5. Since 5 already exists in the set, the algorithm returns True.

Example 2

Input:
root = [5,3,6,2,4,null,7]
k = 28

Current Node	Complement Needed	Seen Set Before	Match Found?
5	23	{}	No
3	25	{5}	No
2	26	{3,5}	No
4	24	{2,3,5}	No
6	22	{2,3,4,5}	No
7	21	{2,3,4,5,6}	No

Traversal finishes without finding any valid pair, so the algorithm returns False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(n)	The hash set may store all node values

The traversal touches every node at most once, and each hash set lookup or insertion takes average constant time. Therefore, the total time complexity is linear.

The space complexity is also linear because, in the worst case, the hash set stores every node value. Additionally, recursive DFS may use up to O(h) call stack space, where h is the tree height. In the worst case of a skewed tree, this becomes O(n).

Test Cases

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

class Solution:
    def findTarget(self, root, k):
        seen = set()

        def dfs(node):
            if not node:
                return False

            if (k - node.val) in seen:
                return True

            seen.add(node.val)

            return dfs(node.left) or dfs(node.right)

        return dfs(root)

sol = Solution()

# Example 1
root1 = TreeNode(5)
root1.left = TreeNode(3)
root1.right = TreeNode(6)
root1.left.left = TreeNode(2)
root1.left.right = TreeNode(4)
root1.right.right = TreeNode(7)

assert sol.findTarget(root1, 9) == True  # pair exists: 2 + 7

# Example 2
assert sol.findTarget(root1, 28) == False  # no valid pair

# Single node tree
root2 = TreeNode(1)

assert sol.findTarget(root2, 2) == False  # cannot reuse same node

# Two node tree with valid answer
root3 = TreeNode(1)
root3.right = TreeNode(3)

assert sol.findTarget(root3, 4) == True  # 1 + 3 = 4

# Negative values
root4 = TreeNode(0)
root4.left = TreeNode(-2)
root4.right = TreeNode(3)

assert sol.findTarget(root4, 1) == True  # -2 + 3 = 1

# No valid pair with negative target
assert sol.findTarget(root4, -10) == False  # impossible target

# Deep skewed tree
root5 = TreeNode(1)
root5.right = TreeNode(2)
root5.right.right = TreeNode(3)
root5.right.right.right = TreeNode(4)

assert sol.findTarget(root5, 7) == True  # 3 + 4 = 7

# Pair involving root
assert sol.findTarget(root1, 11) == True  # 5 + 6 = 11

Test	Why
Balanced BST with valid pair	Verifies normal successful case
Balanced BST without valid pair	Verifies correct false return
Single node tree	Ensures same node is not reused
Two node tree	Smallest possible valid pair
Negative values	Confirms algorithm handles negatives
Impossible negative target	Verifies failure handling
Skewed tree	Tests recursion depth behavior
Pair involving root	Ensures root participates correctly

Edge Cases

Single Node Tree

A tree containing only one node cannot possibly contain two distinct elements whose sum equals k.

A buggy implementation might accidentally allow the same node to be reused twice. For example, if the node value is 5 and k = 10, an incorrect algorithm could mistakenly return True.

This implementation avoids that problem because it checks for the complement before inserting the current node into the hash set. Therefore, the same node cannot match with itself.

Negative Values

The tree may contain negative numbers, and the target k may also be negative.

Some incorrect implementations assume all values are positive or rely on BST ordering in ways that break with negative numbers.

The hash set approach works uniformly for all integers because it only depends on complement arithmetic and hash lookups.

Skewed Trees

A BST may become completely skewed, essentially behaving like a linked list.

For example:

This creates recursion depth equal to the number of nodes.

The algorithm still works correctly because DFS naturally handles arbitrary tree shapes. However, recursive depth may become large in worst-case trees. With the given constraints, this recursive solution is still acceptable for LeetCode.

LeetCode 653 - Two Sum IV - Input is a BST