A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 235. Lowest Common Ancestor of a Binary Search Tree, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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, two pointers, sliding window.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, fillPath, lowestCommonAncestor.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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 (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
03
04According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
05
06Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
07
08Example 1:
09
10Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
11Output: 6
12Explanation: The LCA of nodes 2 and 8 is 6.
13Example 2:
14
15Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
16Output: 2
17Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
18
19Note:
20
21All of the nodes' values will be unique.
22p and q are different and both values will exist in the BST.
23**/
24
25//Runtime: 48 ms, faster than 50.56% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
26//Memory Usage: 27.5 MB, less than 5.39% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
27/**
28 * Definition for a binary tree node.
29 * struct TreeNode {
30 * int val;
31 * TreeNode *left;
32 * TreeNode *right;
33 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
34 * };
35 */
36class Solution {
37public:
38 void dfs(TreeNode* root, int depth, vector<TreeNode*>& visited, vector<int>& depths){
39 if(root==NULL) return;
40 dfs(root->left, depth+1, visited, depths);
41 dfs(root->right, depth+1, visited, depths);
42 visited.push_back(root);
43 depths.push_back(depth+1);
44 }
45
46 void fillPath(vector<TreeNode*>& visited, vector<int>& depths, vector<TreeNode*>& path, TreeNode* node){
47 int depth;
48 for(int i = 0; i < visited.size(); i++){
49 if(visited[i]==node){
50 path.push_back(visited[i]);
51 depth = depths[i];
52 depth--;
53 }else if(depths[i]==depth){
54 path.push_back(visited[i]);
55 depth--;
56 }
57 }
58 }
59
60 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
61 vector<TreeNode*> visited;
62 vector<int> depths;
63
64 dfs(root, 0, visited, depths);
65
66 //record the path to p & q
67 vector<TreeNode*> pPath, qPath;
68 fillPath(visited, depths, pPath, p);
69 fillPath(visited, depths, qPath, q);
70
71 TreeNode* prev = 0;
72 for(int i = 0; i < pPath.size() && i < qPath.size(); i++){
73 if(pPath[pPath.size()-1-i]!=qPath[qPath.size()-1-i]){
74 return prev;
75 }
76 prev = pPath[pPath.size()-1-i];
77 }
78
79 return prev;
80 }
81};
82
83/**
84Approach 1: Recursive Approach
85Intuition
86
87Lowest common ancestor for two nodes p and q would be the last ancestor node common to both of them.
88Here last is defined in terms of the depth of the node.
89The below diagram would help in understanding what lowest means.
90Note: One of p or q would be in the left subtree and the other in the right subtree of the LCA node.
91
92Algorithm
93
94Start traversing the tree from the root node.
95If both the nodes p and q are in the right subtree, then continue the search with right subtree starting step 1.
96If both the nodes p and q are in the left subtree, then continue the search with left subtree starting step 1.
97If both step 2 and step 3 are not true, this means we have found the node which is common to node p's and q's subtrees.
98and hence we return this common node as the LCA.
99**/
100
101/**
102Complexity Analysis
103Time Complexity: O(N), where N is the number of nodes in the BST.
104In the worst case we might be visiting all the nodes of the BST.
105
106Space Complexity: O(N). This is because the maximum amount of space
107utilized by the recursion stack would be NN since the height of a skewed BST could be N.
108**/
109
110//Runtime: 56 ms, faster than 11.43% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
111//Memory Usage: 25.8 MB, less than 63.85% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
112/**
113 * Definition for a binary tree node.
114 * struct TreeNode {
115 * int val;
116 * TreeNode *left;
117 * TreeNode *right;
118 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
119 * };
120 */
121class Solution {
122public:
123 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
124 if(p->val > root->val && q->val > root->val){
125 //both on right side
126 return lowestCommonAncestor(root->right, p, q);
127 }else if(p->val < root->val && q->val < root->val){
128 //both on left side
129 return lowestCommonAncestor(root->left, p, q);
130 // }else if((p->val - root->val) * (q->val - root->val) < 0 || root==p || root==q){
131 }else {
132 //p and q are on the two sides of root
133 //or one of p or q is root
134 return root;
135 }
136 return NULL;
137 }
138};
139
140
141//iterative
142/**
143Approach 2: Iterative Approach
144Algorithm
145
146The steps taken are also similar to approach 1.
147The only difference is instead of recursively calling the function,
148we traverse down the tree iteratively.
149This is possible without using a stack or recursion since we don't need to backtrace to find the LCA node.
150In essence of it the problem is iterative, it just wants us to find the split point.
151The point from where p and q won't be part of the same subtree or when one is the parent of the other.
152**/
153
154//Runtime: 56 ms, faster than 11.43% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
155//Memory Usage: 25.9 MB, less than 34.62% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
156/**
157Complexity Analysis
158Time Complexity : O(N), where N is the number of nodes in the BST.
159In the worst case we might be visiting all the nodes of the BST.
160Space Complexity : O(1).
161**/
162
163/**
164 * Definition for a binary tree node.
165 * struct TreeNode {
166 * int val;
167 * TreeNode *left;
168 * TreeNode *right;
169 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
170 * };
171 */
172class Solution {
173public:
174 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
175 TreeNode* cur = root;
176 while(cur!=NULL){
177 if(p->val > cur->val && q->val > cur->val){
178 cur = cur->right;
179 }else if(p->val < cur->val && q->val < cur->val){
180 cur = cur->left;
181 }else {
182 return cur;
183 }
184 }
185 return NULL;
186 }
187};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.