Let's make this one less mysterious. For 98. Validate Binary Search Tree, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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, stack, sliding window.
The notes already sitting in the source point us in the right direction:
- Naive, only compare with its left and right children
- WA: 70 / 75 test cases passed.
- [10,5,15,null,null,6,20]
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 isValidBST, recurse, inOrder.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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//Naive, only compare with its left and right children
02//WA: 70 / 75 test cases passed.
03//[10,5,15,null,null,6,20]
04class Solution {
05public:
06 bool isValidBST(TreeNode* root) {
07 if(!root) return true;
08 if(root->left && root->left->val >= root->val) return false;
09 if(root->right && root->right->val <= root->val) return false;
10
11 return isValidBST(root->left) && isValidBST(root->right);
12 }
13};
14
15//Recursion
16//Runtime: 8 ms, faster than 99.49% of C++ online submissions for Validate Binary Search Tree.
17//Memory Usage: 22.2 MB, less than 5.05% of C++ online submissions for Validate Binary Search Tree.
18/**
19 * Definition for a binary tree node.
20 * struct TreeNode {
21 * int val;
22 * TreeNode *left;
23 * TreeNode *right;
24 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
25 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
26 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
27 * };
28 */
29class Solution {
30public:
31 bool isValidBST(TreeNode* root, int& minv, int& maxv) {
32 if(!root) return true;
33 if(!root->left && !root->right){
34 minv = maxv = root->val;
35 return true;
36 }else if(root->left && root->right){
37 int minl = INT_MAX, maxl = INT_MIN;
38 //if subtree is invalid, return immediately!!
39 if(!isValidBST(root->left, minl, maxl)) return false;
40 if(maxl >= root->val) return false;
41
42 int minr = INT_MAX, maxr = INT_MIN;
43 if(!isValidBST(root->right, minr, maxr)) return false;
44 if(minr <= root->val) return false;
45
46 minv = minl;
47 maxv = maxr;
48
49 return true;
50 }else if(!root->right){
51 //left subtree is not empty
52 int minl = INT_MAX, maxl = INT_MIN;
53 if(!isValidBST(root->left, minl, maxl)) return false;
54 if(maxl >= root->val) return false;
55 maxv = root->val;
56 minv = minl;
57 return true;
58 }else/* if(!root->left)*/{
59 //right subtree is not empty
60 int minr = INT_MAX, maxr = INT_MIN;
61 if(!isValidBST(root->right, minr, maxr)) return false;
62 if(minr <= root->val) return false;
63 minv = root->val;
64 maxv = maxr;
65 return true;
66 }
67 }
68
69 bool isValidBST(TreeNode* root) {
70 int rootmin = INT_MAX, rootmax = INT_MIN;
71 return isValidBST(root, rootmin, rootmax);
72 }
73};
74
75//Approach 1: Recursion(cleaner)
76//Runtime: 16 ms, faster than 82.11% of C++ online submissions for Validate Binary Search Tree.
77//Memory Usage: 22 MB, less than 15.55% of C++ online submissions for Validate Binary Search Tree.
78//time: O(N), space: O(N)
79class Solution {
80public:
81 bool recurse(TreeNode* node, long long lower, long long upper){
82 if(!node) return true;
83
84 if(node->val <= lower) return false;
85 if(node->val >= upper) return false;
86
87 if(!recurse(node->left, lower, node->val)) return false;
88 if(!recurse(node->right, node->val, upper)) return false;
89
90 return true;
91 }
92
93 bool isValidBST(TreeNode* root) {
94 // cout << LLONG_MIN << endl;
95 // cout << LLONG_MAX << endl;
96 return recurse(root, LLONG_MIN, LLONG_MAX);
97 }
98};
99
100//Approach 2: Iteration
101//Runtime: 20 ms, faster than 56.08% of C++ online submissions for Validate Binary Search Tree.
102//Memory Usage: 22.2 MB, less than 5.05% of C++ online submissions for Validate Binary Search Tree.
103//time: O(N), space: O(N)
104class Solution {
105public:
106 typedef tuple<TreeNode*, long long, long long> tpnlu;
107 bool isValidBST(TreeNode* root) {
108 stack<tpnlu> stk;
109
110 stk.push({root, LLONG_MIN, LLONG_MAX});
111
112 while(!stk.empty()){
113 tpnlu tp = stk.top(); stk.pop();
114 TreeNode* node = get<0>(tp);
115 long long lower = get<1>(tp);
116 long long upper = get<2>(tp);
117
118 if(node == nullptr) continue;
119
120 // cout << lower << ", " << node->val << ", " << upper << endl;
121 if(node->val <= lower) return false;
122 if(node->val >= upper) return false;
123
124 stk.push({node->left, lower, node->val});
125 stk.push({node->right, node->val, upper});
126 }
127
128 return true;
129 }
130};
131
132//Approach 3: Inorder traversal(recursive)
133//Runtime: 20 ms, faster than 56.08% of C++ online submissions for Validate Binary Search Tree.
134//Memory Usage: 22 MB, less than 12.60% of C++ online submissions for Validate Binary Search Tree.
135//time: O(N), space: O(N)
136class Solution {
137public:
138 bool inOrder(TreeNode* node, long long& last){
139 if(!node) return true;
140 if(!inOrder(node->left, last)) return false;
141 // cout << node->val << " " << last << endl;
142
143 //check for current node
144 if(node->val <= last) return false;
145 //update last for its right child and also its parent to its right
146 /*
147 if current node is left child,
148 when it returns to its parent(to its right),
149 "last" will be updated to the max value in that parent's left subtree,
150 then parent's val will be compared with "last"
151
152 if current node is right child,
153 it will return to one of its ancestor to the right
154 */
155 last = node->val;
156
157 if(!inOrder(node->right, last)) return false;
158 return true;
159 }
160
161 bool isValidBST(TreeNode* root) {
162 long long last = LLONG_MIN;
163 return inOrder(root, last);
164 }
165};
166
167//Inorder traversal(iterative)
168//Runtime: 16 ms, faster than 82.11% of C++ online submissions for Validate Binary Search Tree.
169//Memory Usage: 22.1 MB, less than 7.55% of C++ online submissions for Validate Binary Search Tree.
170//time: O(N), space: O(N)
171class Solution {
172public:
173 bool isValidBST(TreeNode* root) {
174 stack<TreeNode*> stk;
175
176 long long last = LLONG_MIN;
177 TreeNode* cur = root;
178
179 while(!stk.empty() || cur){
180 while(cur){
181 stk.push(cur);
182 cur = cur->left;
183 }
184
185 cur = stk.top(); stk.pop();
186
187 if(cur->val <= last) return false;
188 last = cur->val;
189
190 cur = cur->right;
191 }
192
193 return true;
194 }
195};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.