i have been watching this playlist from last 2 week and practicing problems, but now when you tell the split approach i was just stunned and rn im at @5:12 , I paused the video and writing this comment ! Seriously India need more brilliant mentors and teachers like you!
This solution is optimal and works only when the constraint that both the nodes are actually in the tree. While not a better approach than the one shown in this video, I went with implementing a visitor pattern to cover the case where any node is not in the tree. This brings the TC to O(H) and SC to O(H) as well. The idea is to keep an expanding array. During the visit to search first item, we add the value to the array at the end. If not found, return null then and there. Now, initialize a variable idx to -1. Then search for second item, and while visiting each node, check if the array[idx + 1] element is the same as the current node. If yes, increment idx. Finally if the node is not found, or if idx stays at -1, return null. Else you can return array[idx] which is the LCA.
bhaiya Dp kab se ayegi .... tree is about to finish i think ...!! few videos left ......Loved your tree series eagerly waiting for the DP series..... please upload it soon...!! you promised us to upload DP on DIWALI...!!
//Iterative code with less number of comparisons and no stack space class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { int minVal = min(p->val,q->val),maxVal = max(p->val,q->val); while(root) { if(root->valright;//both values are on right of current node else if(root->val>maxVal) root = root->left;//both values are on left of current node else break;//this node is LCA of p and q } return root; } };
// Iterative Approach JAVA: Beats 100%🔥 package DataSructures.BST; public class LCAInBST { // time complexity: O(height) -> not recommended to use the BT way of solving, since it gives tc of O(n) public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode lca = findNode(root, p, q); return lca; } private TreeNode findNode(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; while (root != null) { // this ensures that we reach the lca. Using the property of BST if (root.val >= Math.min(p.val, q.val) && root.val = Math.max(p.val, q.val)) { root = root.left; } else { root = root.right; } } return root; } }
In the code, if we do not write 'return' before recursive calling the lowestCommonAncestor function, then also it is giving correct output. Then what's the purpose of writing it?
No it's not working if you do not write return before recursive call bcz if you will not write return than it will return actual root of bst at the end so its mandatory to write return before recursion as than it will return the root of LCA
![NOSFERATU - Official Trailer [HD] - Only In Theaters December 25](http://i.ytimg.com/vi/nulvWqYUM8k/mqdefault.jpg)
Please do like and share among your friends!! ^ _ ^
Kehne ki baat hai yeh bhii
Iterative Code:
TreeNode *LCAinaBST(TreeNode *root, TreeNode *p, TreeNode *q)
{
while (root)
{
if (root->data > p->data && root->data > q->data)
root = root->left;
else if (root->data < q->data && root->data < p->data)
root = root->right;
else
return root;
}
return NULL;
}
nice explanation....
Hope the haters watch the video once instead of just barging and disliking. Thank you so much bhaiya for such amazing content.
This guy has haters?
He is an inspiration bro🙂
i have been watching this playlist from last 2 week and practicing problems, but now when you tell the split approach i was just stunned and rn im at @5:12 , I paused the video and writing this comment ! Seriously India need more brilliant mentors and teachers like you!
Man u are right. I was stunned for a sec!!
Same man
exactly same experience
Hey striver i followed your entire tree series but still i can't remember some of the concepts in previous videos. What should i do?
Notes..
And Revision...
Same here buddy no one can except if you are prodigy... SO REVISION IS THE KEY
·class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
int current = root.val;
if(currentq.val){
return lowestCommonAncestor(root.left,p,q);
}
else{
return root;
}
}
}
Good explanation .... just one thing bro control your hands movement 😂😂 ... jokes apart..... keep up the good work
Do u read every comments striver, just asking.By the way thanks a lot for #FreekaTreeSeries❤
This solution is optimal and works only when the constraint that both the nodes are actually in the tree. While not a better approach than the one shown in this video, I went with implementing a visitor pattern to cover the case where any node is not in the tree. This brings the TC to O(H) and SC to O(H) as well. The idea is to keep an expanding array. During the visit to search first item, we add the value to the array at the end. If not found, return null then and there. Now, initialize a variable idx to -1. Then search for second item, and while visiting each node, check if the array[idx + 1] element is the same as the current node. If yes, increment idx. Finally if the node is not found, or if idx stays at -1, return null. Else you can return array[idx] which is the LCA.
He had cover this edge test case on Previous LCA video
What if node p is present and node q is not present in the BST
Thank you sooooo much
bhaiya Dp kab se ayegi .... tree is about to finish i think ...!! few videos left ......Loved your tree series eagerly waiting for the DP series..... please upload it soon...!! you promised us to upload DP on DIWALI...!!
I promised if you give me 10k likes, you did not 🥲
Anyways will be up from Dec 1
@@takeUforward bhaiya thodi jldi november m hi upload krdo placement season hai december m 😿. like to bhaiya aa jayenge content hi aise hai 💓.
@@takeUforward apne mera resume roast kardia pr purra nhi dekha :c
//Iterative code with less number of comparisons and no stack space
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int minVal = min(p->val,q->val),maxVal = max(p->val,q->val);
while(root)
{
if(root->valright;//both values are on right of current node
else if(root->val>maxVal)
root = root->left;//both values are on left of current node
else
break;//this node is LCA of p and q
}
return root;
}
};
what in the case of skewed tree like 1->right = 2, 2->right = 3;
It's my solution but it takes O(2h) extra space and O(n) time
class Solution {
private void fillSet(TreeNode root, TreeNode targetNode, Set set) {
TreeNode curr = root;
while (curr != targetNode) {
set.add(curr);
if (targetNode.val < curr.val)
curr = curr.left;
else curr = curr.right;
}
set.add(curr);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
Set setOne = new LinkedHashSet();
Set setTwo = new LinkedHashSet();
fillSet(root, p, setOne);
fillSet(root, q, setTwo);
setOne.retainAll(setTwo);
TreeNode lca = null;
for (TreeNode node : setOne)
lca = node;
return lca;
}
}
loved the intuition, amazing explanation as alwaysss!!!! tysm!!!
Line 13 should be : if(root == NULL) return root ;
U can write return null or return root (both are correct)
Here are my detailed notes on this question:
garmadon.notion.site/Lowest-Common-Ancestor-of-a-Binary-Search-Tree-f568d9e1505f4234bdbd045516e0d4e5
DSA God 😍🙌🚩🚀
Hello sir, thanks for providing such amazing video tutorials. I can't understand why are you writing the base case here? Is there any need to do that?
You can ignore if it works without them, I usually write it for cleaner code
@@takeUforward Thank you sir. Got it. ❤️
Striver bhai c++ pr chal nahi raha hai aapka code
man, u r genius.
what a brilliant way of teaching.
I struggled for 2 hours because I was considering bst as bt.... thank you so much for this...
Amazing video as always, you're tree series is helping a lot 🙂🙂
Keep it up, we need teachers like you!!
can this approach be applied to lca of binary tree
nope
Thanks for this awesome series! you are the best!
Thank you so mcuh for all your hard work !!!
// Iterative Approach JAVA: Beats 100%🔥
package DataSructures.BST;
public class LCAInBST {
// time complexity: O(height) -> not recommended to use the BT way of solving, since it gives tc of O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lca = findNode(root, p, q);
return lca;
}
private TreeNode findNode(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
while (root != null) {
// this ensures that we reach the lca. Using the property of BST
if (root.val >= Math.min(p.val, q.val) && root.val = Math.max(p.val, q.val)) {
root = root.left;
} else {
root = root.right;
}
}
return root;
}
}
Wow!
//clean iterative code
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root){
if(root->val > p->val && root->val > q->val)
root = root->left;
else if(root->val < p->val && root->val < q->val)
root = root->right;
else break;
}
return root ;
}
};
Understood
Hi Striver, if the same question is extended and if they given an array of nodes and if asked to find lca? How to do?
build the BST from array(you need to sort an array) and then perform LCA
@@ashpreetsidana6674 This consume too much time I guess!! Any efficeient way ?
understood
Thanks for this much amazing content and explanation.
Again very grateful 😊
Understood
Understood
Thanks
Nice
This is just outstanding
Understood
understood
Why does it work without the base case check? It works well without `if root == null{return root;}`
because both the nodes exists in the tree is the criteria in leetcode
super explaination bro🙏
what if p and q are not present in BST ??
Man, really good stuff!! Thank you for this!
I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?
hell,yes...!!
crystal clear explanation. Thank you Striver.
bhai kaafi pro level intuition h
Thanks!
soooo goood trulyyy
Great Series 😀
1 is missing bro pls correct it
Thanks for the video:)
able to solve by myself
link of the question ?
shit got real, nice1
I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?
Thank you Bhaiya
In the code, if we do not write 'return' before recursive calling the lowestCommonAncestor function, then also it is giving correct output. Then what's the purpose of writing it?
No it's not working if you do not write return before recursive call bcz if you will not write return than it will return actual root of bst at the end so its mandatory to write return before recursion as than it will return the root of LCA
phele se sb krke baitha h bhai? : (
Thank you sir
bro is genius .
nice solution
thanks bhaiya
Thanks for such a nice explanation!
u r the besttt
good job :)
understood
understood
Awesome code,video keep it uo
thank you
thank you Bhaiya
if the given p and q nodes is not there .what we need to do?
return -1
thanks
Tq sir
Super
Understood:)
Understood
US
Very clear explanation
thanks mate!
UnderStood
understood
"us"
Understood🔥
💚
great
Amazing sir
🔥🔥❤️
tc = logn right?
No, think of shew bst it will be o(n)
@@only_for_fun1234r yes you are right . thanx
striver runs java code in c++ mode (7:52) on leetcode, halke me mt lena god hai bro apna
geeks for geeks accepted solution using while loop ...hope this helps...
Node* LCA(Node *root, int n1, int n2)
{
//Your code here
while(root){
if(root->data==n1 || root->data==n2) {
return root;
}
else if(root->data>n1 && root->datadatadata>n2){
return root;
}
else if(root->data>n1){
root=root->left;
}
else{
root=root->right;
}
}
}