Two Sum IV - Input is a BST - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree is in the range
[1, 104]. -104 <= Node.val <= 104rootis guaranteed to be a valid binary search tree.-105 <= k <= 105
Approach Overview
Problem 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 1: Inorder Traversal with Two-Pointer Technique
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.
Complexity
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.
Approach 2: BST and HashSet Complement Search
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.
Complexity
Time Complexity: O(n), with a pass through each node.
Space Complexity: O(n) for storing nodes in the hash table.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode - Two Sum IV - Input is a BST (Python) • Timothy H Chang • 5,387 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Two Sum IV - Input is a BST easy or hard?
How to solve Two Sum IV - Input is a BST in O(n)?
Two Sum IV - Input is a BST Python or Java solution?
What is the best approach for Two Sum IV - Input is a BST?
Is Two Sum IV - Input is a BST asked at Google/Amazon/Meta?
What data structure is used in Two Sum IV - Input is a BST?
What is the time complexity of Two Sum IV - Input is a BST?
Ready to solve this problem?
Practice Two Sum IV - Input is a BST with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor