This is one of those problems where the clean idea matters more than the amount of code. For 653. Two Sum IV - Input is a BST, the solution in this repository is mainly a two pointers solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, sliding window.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findTarget, inOrder.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
03
04Example 1:
05
06Input:
07 5
08 / \
09 3 6
10 / \ \
112 4 7
12
13Target = 9
14
15Output: True
16
17
18Example 2:
19
20Input:
21 5
22 / \
23 3 6
24 / \ \
252 4 7
26
27Target = 28
28
29Output: False
30**/
31
32//Runtime: 48 ms, faster than 96.64% of C++ online submissions for Two Sum IV - Input is a BST.
33//Memory Usage: 27.3 MB, less than 64.61% of C++ online submissions for Two Sum IV - Input is a BST.
34
35/**
36 * Definition for a binary tree node.
37 * struct TreeNode {
38 * int val;
39 * TreeNode *left;
40 * TreeNode *right;
41 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
42 * };
43 */
44class Solution {
45public:
46 bool findTarget(TreeNode* root, int k) {
47 queue<TreeNode*> q;
48 vector<int> v; //values seen
49 TreeNode* cur;
50
51 q.push(root);
52
53 while(!q.empty()){
54 cur = q.front();
55 q.pop();
56
57 for(int e : v){
58 if(e+cur->val==k){
59 return true;
60 }
61 }
62 v.push_back(cur->val);
63
64 if(cur->left) q.push(cur->left);
65 if(cur->right) q.push(cur->right);
66 }
67
68 return false;
69 }
70};
71
72/**
73Approach #1 Using HashSet[Accepted]
74The simplest solution will be to traverse over the whole tree and consider every possible pair of nodes to determine
75if they can form the required sum kk. But, we can improve the process if we look at a little catch here.
76
77If the sum of two elements x + yx+y equals kk, and we already know that xx exists in the given tree,
78we only need to check if an element yy exists in the given tree, such that y = k - xy=k−x.
79Based on this simple catch, we can traverse the tree in both the directions(left child and right child) at every step.
80We keep a track of the elements which have been found so far during the tree traversal, by putting them into a setset.
81
82For every current node with a value of pp, we check if k-pk−p already exists in the array.
83If so, we can conclude that the sum kk can be formed by using the two elements from the given tree.
84Otherwise, we put this value pp into the setset.
85
86If even after the whole tree's traversal, no such element pp can be found, the sum kk can't be formed by using any two elements.
87**/
88
89/**
90Complexity Analysis
91
92Time complexity : O(n)O(n). The entire tree is traversed only once in the worst case.
93Here, nn refers to the number of nodes in the given tree.
94
95Space complexity : O(n)O(n). The size of the setset can grow upto nn in the worst case.
96**/
97
98/**
99Approach #2 Using BFS and HashSet [Accepted]
100Algorithm
101
102In this approach, the idea of using the setset is the same as in the last approach.
103But, we can carry on the traversal in a Breadth First Search manner,
104which is a very common traversal method used in Trees.
105The way BFS is used can be summarized as given below.
106We start by putting the root node into a queuequeue.
107We also maintain a setset similar to the last approach.
108Then, at every step, we do as follows:
109
110Remove an element, pp, from the front of the queuequeue.
111
112Check if the element k-pk−p already exists in the setset. If so, return True.
113
114Otherwise, add this element, pp to the setset. Further,
115add the right and the left child nodes of the current node to the back of the queuequeue.
116
117Continue steps 1. to 3. till the queuequeue becomes empty.
118
119Return false if the queuequeue becomes empty.
120
121By following this process, we traverse the tree on a level by level basis.
122**/
123
124/**
125Complexity Analysis
126
127Time complexity : O(n)O(n). We need to traverse over the whole tree once in the worst case. Here, nn refers to the number of nodes in the given tree.
128
129Space complexity : O(n)O(n). The size of the setset can grow atmost upto nn.
130**/
131
132/**
133class Solution {
134public:
135 bool findTarget(TreeNode* root, int k) {
136 queue<TreeNode*> q;
137 set<int> myset; //values seen
138 TreeNode* cur;
139
140 q.push(root);
141
142 while(!q.empty()){
143 cur = q.front();
144 q.pop();
145 if(cur==NULL) break;
146
147 if(myset.find(k-cur->val)!=myset.end()){
148 return true;
149 }
150 myset.insert(cur->val);
151
152 if(cur->left) q.push(cur->left);
153 if(cur->right) q.push(cur->right);
154 }
155
156 return false;
157 }
158};
159**/
160
161/**
162Approach #3 Using BST [Accepted]
163Algorithm
164
165In this approach, we make use of the fact that the given tree is a Binary Search Tree. Now, we know that the inorder traversal of a BST gives the nodes in ascending order. Thus, we do the inorder traversal of the given tree and put the results in a listlist which contains the nodes sorted in ascending order.
166
167Once this is done, we make use of two pointers ll and rr pointing to the beginning and the end of the sorted listlist. Then, we do as follows:
168
169Check if the sum of the elements pointed by ll and rr is equal to the required sum kk. If so, return a True immediately.
170
171Otherwise, if the sum of the current two elements is lesser than the required sum kk, update ll to point to the next element. This is done, because, we need to increase the sum of the current elements, which can only be done by increasing the smaller number.
172
173Otherwise, if the sum of the current two elements is larger than the required sum kk, update rr to point to the previous element. This is done, because, we need to decrease the sum of the current elements, which can only be done by reducing the larger number.
174
175Continue steps 1. to 3. till the left pointer ll crosses the right pointer rr.
176
177If the two pointers cross each other, return a False value.
178
179Note that we need not increase the larger number or reduce the smaller number in any case. This happens because, in case, a number larger than the current list[r]list[r] is needed to form the required sum kk, the right pointer could not have been reduced in the first place. The similar argument holds true for not reducing the smaller number as well.
180**/
181
182/**
183Complexity Analysis
184
185Time complexity : O(n)O(n).
186We need to traverse over the whole tree once to do the inorder traversal.
187Here, nn refers to the number of nodes in the given tree.
188
189Space complexity : O(n)O(n).
190The sorted listlist will contain nn elements.
191**/
192
193/**
194class Solution {
195public:
196 void inOrder(TreeNode* root, vector<int>& v){
197 if(root==NULL) return;
198 if(root->left) inOrder(root->left, v);
199 v.push_back(root->val);
200 if(root->right) inOrder(root->right, v);
201 }
202
203 bool findTarget(TreeNode* root, int k) {
204 vector<int> v;
205 inOrder(root, v);
206
207 int l = 0, r = v.size()-1;
208
209 while(l<r){
210 if(v[l] + v[r] == k){
211 return true;
212 }else if(v[l] + v[r] < k){
213 l++;
214 }else{
215 r--;
216 }
217 }
218
219 return false;
220 }
221};
222**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.