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.
great explanation but one catch is we're missing/skipping the edge case , whether the nodes actually exist after the splitting node , cause the function might return the LCA even if one of the two p or q is actually missing in the tree , for that we have to right a check function before running the lca function bool exists(Node* root, int val) { while (root != NULL) { if (root->data == val) return true; // Node found else if (val < root->data) root = root->left; // Search in left subtree else root = root->right; // Search in right subtree } return false; // Node not found } // Function to find the LCA Node* lca(Node* root, int p, int q) { while (root != NULL) { if (root->data > p && root->data > q) { root = root->left; } else if (root->data < p && root->data < q) { root = root->right; } else { return root; // Found the LCA } } return NULL; // If the LCA is not found } int main() { Node* root = new Node(20); root->left = new Node(10); root->right = new Node(30); root->left->left = new Node(5); root->left->right = new Node(15); root->right->right = new Node(40); int p = 5; int q = 2; // Testing edge case where one node (2) does not exist in the tree // Verify existence of both nodes if (exists(root, p) && exists(root, q)) { Node* result = lca(root, p, q); if (result == NULL) { cout
//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; } };
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...!!
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
// 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; } }
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;
}
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
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
Perfect
man, u r genius.
what a brilliant way of teaching.
Thanks Stirver for Tree ka playlist i was able to solve this problem by myself. Thanks a lot.
I struggled for 2 hours because I was considering bst as bt.... thank you so much for this...
Great Series 😀
Man, really good stuff!! Thank you for this!
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🙂
great explanation but one catch is we're missing/skipping the edge case , whether the nodes actually exist after the splitting node , cause the function might return the LCA even if one of the two p or q is actually missing in the tree , for that we have to right a check function before running the lca function
bool exists(Node* root, int val) {
while (root != NULL) {
if (root->data == val) return true; // Node found
else if (val < root->data) root = root->left; // Search in left subtree
else root = root->right; // Search in right subtree
}
return false; // Node not found
}
// Function to find the LCA
Node* lca(Node* root, int p, int q) {
while (root != NULL) {
if (root->data > p && root->data > q) {
root = root->left;
} else if (root->data < p && root->data < q) {
root = root->right;
} else {
return root; // Found the LCA
}
}
return NULL; // If the LCA is not found
}
int main() {
Node* root = new Node(20);
root->left = new Node(10);
root->right = new Node(30);
root->left->left = new Node(5);
root->left->right = new Node(15);
root->right->right = new Node(40);
int p = 5;
int q = 2; // Testing edge case where one node (2) does not exist in the tree
// Verify existence of both nodes
if (exists(root, p) && exists(root, q)) {
Node* result = lca(root, p, q);
if (result == NULL) {
cout
Great approach
Good explanation .... just one thing bro control your hands movement 😂😂 ... jokes apart..... keep up the good work
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
Keep it up, we need teachers like you!!
Thank you sooooo much
super explaination bro🙏
Nice
nice solution
Amazing video as always, you're tree series is helping a lot 🙂🙂
Thank you So much !
Thanks for this awesome series! you are the best!
bro is genius .
Do u read every comments striver, just asking.By the way thanks a lot for #FreekaTreeSeries❤
Amazing sir
loved the intuition, amazing explanation as alwaysss!!!! tysm!!!
Understood🔥
·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;
}
}
}
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. ❤️
good job :)
what if p and q are not present in BST ??
Wow!
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 ?
What if node p is present and node q is not present in the BST
thank you Bhaiya
crystal clear explanation. Thank you Striver.
Understood
what in the case of skewed tree like 1->right = 2, 2->right = 3;
Thanks
thank you
//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;
}
};
Thanks for this much amazing content and explanation.
Again very grateful 😊
link of the question ?
can this approach be applied to lca of binary tree
nope
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
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? : (
Thanks for such a nice explanation!
Very clear explanation
bhai kaafi pro level intuition h
Thanks!
understood
Thank you so mcuh for all your hard work !!!
submit bhi n hua y toh
striver runs java code in c++ mode (7:52) on leetcode, halke me mt lena god hai bro apna
1 is missing bro pls correct it
I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?
if the given p and q nodes is not there .what we need to do?
return -1
DSA God 😍🙌🚩🚀
Striver bhai c++ pr chal nahi raha hai aapka code
This is just outstanding
nice explanation....
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
tc = logn right?
No, think of shew bst it will be o(n)
@@only_for_fun1234r yes you are right . thanx
thanks bhaiya
US
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;
}
}
thanks
Line 13 should be : if(root == NULL) return root ;
U can write return null or return root (both are correct)
Thanks for the video:)
thanks mate!
Thank you sir
understood
//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 ;
}
};
Thank you Bhaiya
Tq sir
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;
}
}
}
Awesome code,video keep it uo
Is this correct?
TC-> O(H)
SC-> O(1) // Iterative soltion
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(true){
if(root==null) return null;
if((root.val>p.val && root.val p.val && root.val>p.val) root=root.left;
else root=root.right;
}
}
}
Understood
💚
u r the besttt
soooo goood trulyyy
🔥🔥❤️
great
Super
able to solve by myself
Understood:)
shit got real, nice1
// 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;
}
}
UnderStood
"us"
Here are my detailed notes on this question:
garmadon.notion.site/Lowest-Common-Ancestor-of-a-Binary-Search-Tree-f568d9e1505f4234bdbd045516e0d4e5
Understood
understood
I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?
hell,yes...!!
understood
Understood
Understood
understood
Understood