Let's make this one less mysterious. For 236. Lowest Common Ancestor of a Binary Tree, the solution in this repository is mainly a graph traversal 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: graph traversal, binary search, two pointers, stack.
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 lowestCommonAncestor, recurseTree.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- 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 stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
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//Runtime: 40 ms, faster than 12.32% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
02//Memory Usage: 15.9 MB, less than 100.00% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
03/**
04 * Definition for a binary tree node.
05 * struct TreeNode {
06 * int val;
07 * TreeNode *left;
08 * TreeNode *right;
09 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10 * };
11 */
12class Solution {
13public:
14 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
15 int pLevel = -1, qLevel = -1;
16
17 queue<TreeNode*> bfsq;
18 TreeNode* cur;
19 int levelCount = 0;
20 int level = 0;
21 map<TreeNode*, TreeNode*> parents;
22
23 bfsq.push(root);
24 parents[root] = nullptr;
25 levelCount++;
26
27 while(!bfsq.empty()){
28 // cout << level << " " << levelCount << endl;
29 while(levelCount-- > 0){
30 cur = bfsq.front(); bfsq.pop();
31 if(cur == p){
32 pLevel = level;
33 }
34 if(cur == q){
35 qLevel = level;
36 }
37 if(cur->left){
38 bfsq.push(cur->left);
39 parents[cur->left] = cur;
40 }
41 if(cur->right){
42 bfsq.push(cur->right);
43 parents[cur->right] = cur;
44 }
45 }
46 level++;
47 levelCount = bfsq.size();
48 }
49
50 //lift the lower one to the same level
51 while(qLevel > pLevel){
52 qLevel--;
53 q = parents[q];
54 }
55
56 while(pLevel > qLevel){
57 pLevel--;
58 p = parents[p];
59 }
60
61 //now p and q are at same level
62 if(p == q) return p;
63
64 while(p != q){
65 p = parents[p];
66 q = parents[q];
67 }
68
69 // cout << pLevel << " " << qLevel << endl;
70
71 return p;
72 }
73};
74
75//Approach 1: Recursive Approach
76//Runtime: 20 ms, faster than 79.55% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
77//Memory Usage: 14.3 MB, less than 100.00% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
78//time: O(N), space: O(N)
79/**
80 * Definition for a binary tree node.
81 * struct TreeNode {
82 * int val;
83 * TreeNode *left;
84 * TreeNode *right;
85 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
86 * };
87 */
88class Solution {
89public:
90 TreeNode *p, *q, *ans;
91
92 bool recurseTree(TreeNode* cur){
93 if(cur == nullptr) return false;
94
95 int mid = (int)(cur == p || cur == q);
96 int left = (int)recurseTree(cur->left);
97 int right = (int)recurseTree(cur->right);
98
99 /*
100 mid & left : current node is lca
101 mid & right: current node is lca
102 left& right: their parent, which is current node, is lca
103 */
104 if(mid + left + right >= 2){
105 ans = cur;
106 }
107
108 //if itself or one of its children is p or q's ancestor
109 return mid + left + right > 0;
110 };
111
112 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
113 this->p = p;
114 this->q = q;
115 recurseTree(root);
116 return ans;
117 }
118};
119
120//Approach 2: Iterative using parent pointers
121//Runtime: 44 ms, faster than 10.21% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
122//Memory Usage: 17.8 MB, less than 20.00% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
123//time: O(N), space: O(N)
124/**
125 * Definition for a binary tree node.
126 * struct TreeNode {
127 * int val;
128 * TreeNode *left;
129 * TreeNode *right;
130 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
131 * };
132 */
133class Solution {
134public:
135 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
136 unordered_map<TreeNode*, TreeNode*> parents;
137 stack<TreeNode*> stk;
138 TreeNode *cur;
139
140 parents[root] = nullptr;
141 stk.push(root);
142
143 //either p or q is not visited
144 while(parents.find(p) == parents.end() || parents.find(q) == parents.end()){
145 cur = stk.top(); stk.pop();
146
147 if(cur->left){
148 parents[cur->left] = cur;
149 stk.push(cur->left);
150 }
151 if(cur->right){
152 parents[cur->right] = cur;
153 stk.push(cur->right);
154 }
155 }
156
157 //record all p's ancestors(including itself) into a set
158 set<TreeNode*> pAncestors;
159 while(p){
160 pAncestors.insert(p);
161 p = parents[p];
162 }
163
164 //find q's least ancestor which is also p's ancestor
165 while(pAncestors.find(q) == pAncestors.end()){
166 q = parents[q];
167 }
168
169 return q;
170 }
171};
172
173//Approach 3: Iterative without parent pointers
174//Runtime: 28 ms, faster than 19.72% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
175//Memory Usage: 15.1 MB, less than 100.00% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
176//time: O(N), space: O(N)
177/**
178 * Definition for a binary tree node.
179 * struct TreeNode {
180 * int val;
181 * TreeNode *left;
182 * TreeNode *right;
183 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
184 * };
185 */
186enum class State{
187 BP, //BOTH_PENDING
188 LD, //LEFT_DONE
189 BD //BOTH_DONE
190};
191
192class Solution {
193public:
194 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
195 stack<pair<TreeNode*, State>> stk;
196
197 stk.push(make_pair(root, State::BP));
198 bool foundOne = false; //either found p or q
199 TreeNode* LCA = nullptr;
200 TreeNode *cur = nullptr, *child = nullptr;
201 State curState;
202
203 while(!stk.empty()){
204 pair<TreeNode*, State> top = stk.top();
205 cur = top.first;
206 curState = top.second;
207
208 if(curState != State::BD){
209 if(curState == State::BP){
210 if(cur == p || cur == q){
211 if(foundOne){
212 //we have found the second
213 return LCA;
214 }else{
215 foundOne = true;
216 LCA = cur;
217 }
218 }
219
220 child = cur->left;
221 }else{
222 child = cur->right;
223 }
224
225 //revise cur's state
226 stk.pop();
227 stk.push(make_pair(cur, (State)((int)curState+1)));
228
229 if(child){
230 stk.push(make_pair(child, State::BP));
231 }
232 }else{
233 TreeNode* tmp = stk.top().first;
234 stk.pop();
235 if(LCA == tmp && foundOne){
236 LCA = stk.top().first;
237 }
238 }
239 }
240
241 return nullptr;
242 }
243};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.