Watch 10 video solutions for Two Sum IV - Input is a BST, a easy level problem involving Hash Table, Two Pointers, Tree. This walkthrough by Timothy H Chang has 5,239 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false
Constraints:
[1, 104].-104 <= Node.val <= 104root is guaranteed to be a valid binary search tree.-105 <= k <= 105Problem Overview: Given the root of a Binary Search Tree and an integer k, determine whether two distinct nodes in the tree add up to the target value. You must check if any pair of values in the BST satisfies node1.val + node2.val = k.
Approach 1: BST and HashSet Complement Search (O(n) time, O(n) space)
This approach treats the tree similarly to the classic Two Sum problem. Traverse the tree using Depth-First Search or Breadth-First Search. While visiting each node, compute the complement k - node.val and check if it already exists in a HashSet. If it does, you found a valid pair and can return true immediately. Otherwise, insert the current value into the set and continue traversing. Hash lookups run in constant time, so every node is processed once. This approach is simple, easy to implement, and works even if the tree is not balanced.
The key insight: instead of comparing every pair of nodes, store previously seen values and perform a constant-time lookup for the complement. The BST property is not heavily used here; the algorithm works on any binary tree. Time complexity is O(n) because each node is visited once. Space complexity is O(n) due to the HashSet storing up to all node values.
Approach 2: Inorder Traversal with Two-Pointer Technique (O(n) time, O(n) space)
This approach leverages the sorted nature of a Binary Search Tree. Perform an inorder traversal to collect all node values in a sorted array. Inorder traversal of a BST naturally produces values in ascending order. Once the array is built, apply the classic two-pointer technique: place one pointer at the start and another at the end of the array. Compute the sum of the two values and compare it with k.
If the sum equals k, a valid pair exists. If the sum is smaller than k, move the left pointer forward to increase the sum. If the sum is larger, move the right pointer backward to decrease the sum. Each pointer moves at most n times, so the scan runs in linear time. The traversal plus the two-pointer scan results in O(n) time overall with O(n) extra space for the array.
This technique explicitly uses the sorted order property of the BST and mirrors the optimal strategy for the classic Two Sum problem on a sorted array. It also avoids hash lookups and can be easier to reason about when debugging.
Recommended for interviews: The HashSet approach is usually the first solution interviewers expect because it directly mirrors the classic Two Sum pattern and is quick to implement during a coding interview. The inorder + two-pointer approach demonstrates deeper understanding of the BST ordering property and shows you can transform a tree problem into an array problem. Mentioning both solutions signals strong problem-solving depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BST with HashSet Complement Search | O(n) | O(n) | Best general solution. Fast to implement during interviews and works for any binary tree. |
| Inorder Traversal + Two Pointers | O(n) | O(n) | When you want to leverage BST sorted order and apply the classic two-pointer pattern. |