#653

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Two Sum IV - Input is a BST

Determine if a binary search tree contains two nodes whose values sum to a target using efficient traversal and state tracking.

hash table two pointers tree depth first search breadth first search

Problem Statement

Given a binary search tree (BST) root and an integer k, return true if there are two nodes whose values sum to k, otherwise return false. Each node value must be considered exactly once, and duplicate counting is not allowed.

You are guaranteed that the tree is a valid BST, and all node values are within the range [-104, 104]. Optimize your solution using tree traversal patterns and state tracking to handle large trees efficiently.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-104 <= Node.val <= 104
root is guaranteed to be a valid binary search tree.
-105 <= k <= 105

Solution Approach

Hash Set During DFS

Traverse the BST with depth-first search and store each visited node's value in a Hash Set. For each node, check if k minus the node's value already exists in the set. If found, return true immediately. This approach leverages constant-time lookups to detect complements efficiently.

Two-Pointer In-Order Traversal

Perform in-order traversal to generate a sorted list of BST values. Use two pointers at the start and end of the list to find a pair summing to k. Move pointers inward based on the sum comparison. This method reduces repeated complement checks and maintains O(n) time and space complexity.

Recursive Complement Tracking

Recursively explore left and right subtrees, passing a set of previously visited values. At each step, check if the current node's complement exists in the set. Propagate the set through recursive calls to avoid global state, maintaining clarity and correctness for complex tree shapes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n) for single-pass DFS or in-order list creation. Space complexity is O(n) for the Hash Set or sorted list to track visited node values. Recursive stack depth may add O(h) space, where h is the tree height.

What Interviewers Usually Probe

They may ask about handling duplicates or repeated values in the BST.
They could probe whether in-order traversal or DFS is preferred for space efficiency.
Expect questions about trade-offs between Hash Set lookup and two-pointer in-order strategies.

Common Pitfalls or Variants

Common pitfalls

Failing to check for the complement before adding the current node value to the Hash Set.
Confusing BST property with binary tree: in-order sorting only works due to BST ordering.
Attempting two-pointer logic without converting the BST to a sorted list, leading to incorrect index references.

Follow-up variants

BST contains negative values or zeros, testing complement detection logic.
The tree is unbalanced or skewed, affecting recursion stack depth and traversal order.
Return all unique pairs summing to k instead of a boolean result.

FAQ

Can Two Sum IV - Input is a BST be solved without extra space?

Yes, using a controlled in-order traversal with two stacks or iterative two-pointer method, but it requires careful pointer management to avoid extra arrays.

What is the difference between using DFS with a Hash Set and two-pointer in-order for this problem?

DFS with Hash Set checks complements on the fly with O(n) time and O(n) space, while in-order two-pointer requires building a sorted list first, also O(n) space, but can be more intuitive for ordered data.

How do duplicates affect the solution?

Since the problem asks for two distinct nodes summing to k, duplicates can be part of a valid pair only if they are separate nodes; failing to distinguish nodes may give incorrect results.

Is this approach applicable to regular binary trees?

Yes, but you cannot rely on in-order traversal to produce a sorted list; complement tracking with a Hash Set is safer for generic binary trees.

What is the main pattern to recognize in Two Sum IV - Input is a BST?

The key pattern is binary-tree traversal combined with state tracking of previously seen node values to detect pairs summing to k efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        def dfs(root):
            if root is None:
                return False
            if k - root.val in vis:
                return True
            vis.add(root.val)
            return dfs(root.left) or dfs(root.right)

        vis = set()
        return dfs(root)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        def dfs(root):
            if root is None:
                return False
            if k - root.val in vis:
                return True
            vis.add(root.val)
            return dfs(root.left) or dfs(root.right)

        vis = set()
        return dfs(root)

Continue Practicing

#530 minimum absolute difference in bst #783 minimum distance between bst nodes #449 serialize and deserialize bst