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.
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.
This C solution first performs an inorder traversal to convert the BST into a sorted array. With two pointers, it iterates over the array to find if a pair exists that sums up to k.
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.
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.
This C solution builds upon a hash table for constant time lookups of complements (values such that k - node.val). For brevity, hash table methods are assumed implemented.
Time Complexity: O(n), with a pass through each node.
Space Complexity: O(n) for storing nodes in the hash table.
| Approach | Complexity |
|---|---|
| Inorder Traversal with Two-Pointer Technique | Time Complexity: Perform O(n) for traversal and O(n) for two-pointer scan, hence O(n). |
| BST and HashSet Complement Search | Time Complexity: O(n), with a pass through each node. |
| Default Approach | — |
| 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. |
Leetcode - Two Sum IV - Input is a BST (Python) • Timothy H Chang • 5,239 views views
Watch 9 more video solutions →Practice Two Sum IV - Input is a BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor