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 <= 105The goal in #653 Two Sum IV - Input is a BST is to determine whether there exist two nodes in a Binary Search Tree whose values sum to a given target. A common strategy is to traverse the tree using Depth-First Search (DFS) while storing visited node values in a HashSet. For each node, check if target - node.val already exists in the set. If it does, a valid pair has been found.
Another approach leverages the Binary Search Tree property. Perform an inorder traversal to extract the node values in sorted order. Then apply the classic two-pointer technique on the sorted list to search for a pair that sums to the target. This mirrors the well-known Two Sum pattern but uses BST ordering.
The DFS + hash set method runs in O(n) time with O(n) space, while the inorder + two-pointer method also runs in O(n) time but requires storing the traversal result.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Hash Set | O(n) | O(n) |
| Inorder Traversal + Two Pointers | O(n) | O(n) |
take U forward
This approach leverages the properties of a Binary Search Tree (BST). By performing an inorder traversal on a BST, we can obtain a sorted list of its elements. Once we have this sorted list, the problem reduces to finding two distinct numbers in this sorted array that sum up to the given target, k. This can efficiently be solved using the two-pointer technique.
Time Complexity: Perform O(n) for traversal and O(n) for two-pointer scan, hence O(n).
Space Complexity: O(n) to store the elements of the tree.
1#include <vector>
2#include <iostream>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11void inorder(TreeNode* root, std::vector<int>& nums) {
12 if (!root) return;
13 inorder(root->left, nums);
14 nums.push_back(root->val);
inorder(root->right, nums);
}
bool findTarget(TreeNode* root, int k) {
std::vector<int> nums;
inorder(root, nums);
int l = 0, r = nums.size() - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == k) return true;
else if (sum < k) l++;
else r--;
}
return false;
}
In this C++ solution, we collect the sorted elements using an inorder traversal. The two-pointer technique is used for finding two numbers summing to k.
This approach utilizes a hash set to store visited node values. We traverse the BST and for each node, check if k - node.val exists in the hash set. If it does, then a pair adding to k has been found.
Time Complexity: O(n), with a pass through each node.
Space Complexity: O(n) for storing nodes in the hash table.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Two Sum problem and BST traversal questions frequently appear in technical interviews, including FAANG-style interviews. This problem tests understanding of trees, hashing, and algorithmic patterns.
A common optimal approach is performing a DFS traversal while storing visited values in a hash set. For each node, check if the complement (target minus current value) exists in the set. This allows you to detect a valid pair in O(n) time.
A hash set is typically the most effective data structure because it allows constant-time lookups for complements. This makes it easy to check whether a matching value has already been seen during traversal.
Yes. By performing an inorder traversal, you can convert the BST into a sorted list. After that, a two-pointer technique can be applied to efficiently find whether two numbers sum to the target.
By storing visited values in a set, the Python solution keeps track of necessary complements, rapidly determining whether k can be formed.