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 <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
L51. Two Sum In BST | Check if there exists a pair with Sum K • take U forward • 177,528 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