L47. LCA in Binary Search Tree

Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements

[@takeUforward]

Please do like and share among your friends!! ^ _ ^

[@danceofficial3912]

Kehne ki baat hai yeh bhii

[@divyansh2212]

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; }

[@SriHarshaChilakapati]

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.

[@crazycr7331]

He had cover this edge test case on Previous LCA video

[@galleryofjatin19]

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!

[@kushalroy9747]

Man u are right. I was stunned for a sec!!

[@VikasGupta-ok9lh]

Same man

[@nikhilmadaan29]

exactly same experience

[@shubhamkumarsingh8818]

man, u r genius. what a brilliant way of teaching.

[@karthik-varma-1579]

Thanks Stirver for Tree ka playlist i was able to solve this problem by myself. Thanks a lot.

[@prajapati-suraj]

I struggled for 2 hours because I was considering bst as bt.... thank you so much for this...

[@aaluSandwich]

Hope the haters watch the video once instead of just barging and disliking. Thank you so much bhaiya for such amazing content.

[@VinayKumar-ze2ww]

This guy has haters? He is an inspiration bro🙂

[@SibiRanganathL]

Great approach

[@priyankasetiya1358]

·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; } } }

[@culeforever5408]

Great Series 😀

[@diegolikescode]

Man, really good stuff!! Thank you for this!

[@amanjotsingh5876]

Good explanation .... just one thing bro control your hands movement 😂😂 ... jokes apart..... keep up the good work

[@vivekjaiswar6825]

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?

[@takeUforward]

Notes..

[@real-investment-banker]

And Revision...

[@codding32world50]

Same here buddy no one can except if you are prodigy... SO REVISION IS THE KEY

[@avanishmaurya2034]

Nice

[@subirkumar6786]

What if node p is present and node q is not present in the BST

[@GauravGangwar-r2v]

bro is genius .

[@priyankaranawat8373]

Thank you sooooo much

[@ishwaripednekar5164]

Keep it up, we need teachers like you!!

[@aaranyaksantra9933]

nice solution

[@himanshidafouty347]

Understood

[@Preethamdivakar]

super explaination bro🙏

[@shwetanksingh5208]

//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; } };

[@nishant1720]

what in the case of skewed tree like 1->right = 2, 2->right = 3;

[@apmotivationakashparmar722]

Thank you So much !

[@zeyadalbadawy2245]

Amazing sir

[@arpanseal5722]

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?

[@takeUforward]

You can ignore if it works without them, I usually write it for cleaner code

[@arpanseal5722]

@@takeUforward Thank you sir. Got it. ❤️

[@GhostVaibhav]

Understood🔥

[@Shubham-yc6nz]

Thanks

[@babai2196]

can this approach be applied to lca of binary tree

[@khitijkarmakar]

nope

[@iamnottech8918]

Wow!

[@Learnprogramming-q7f]

thank you Bhaiya

[@hakunamatata-nl4js]

thank you

[@ishangujarathi10]

loved the intuition, amazing explanation as alwaysss!!!! tysm!!!

[@arpanbanejee5143]

Thanks for this awesome series! you are the best!

[@harshitjaiswal9439]

understood

[@ashishchandra4078]

crystal clear explanation. Thank you Striver.

[@swayam50]

Amazing video as always, you're tree series is helping a lot 🙂🙂

[@shikharai-tl4vb]

good job :)

[@saranguru6100]

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?

[@ashpreetsidana6674]

build the BST from array(you need to sort an array) and then perform LCA

[@saranguru6100]

​@@ashpreetsidana6674 This consume too much time I guess!! Any efficeient way ?

[@editorera239]

bhai kaafi pro level intuition h Thanks!

[@ashuraj1981]

Do u read every comments striver, just asking.By the way thanks a lot for #FreekaTreeSeries❤

[@akashnandi1267]

1 is missing bro pls correct it

[@RAJKUMAR-q4c2x]

what if p and q are not present in BST ??

[@codebits2120]

Very clear explanation

[@rishabhprasad8333]

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?

[@MeenakshiSharma-bd3bu]

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

[@lakshayrastogi2347]

phele se sb krke baitha h bhai? : (

[@chirlasowmyareddy]

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; } } }

[@thebibeksaha]

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; } }

[@parthsalat]

Here are my detailed notes on this question: garmadon.notion.site/Lowest-Common-Ancestor-of-a-Binary-Search-Tree-f568d9e1505f4234bdbd045516e0d4e5

[@tech_wizard9315]

I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?

[@Kpriyasing]

Thanks for such a nice explanation!

[@krishnarajs929]

if the given p and q nodes is not there .what we need to do?

[@optimus_prime01]

return -1

[@kwakubiney5175]

Why does it work without the base case check? It works well without `if root == null{return root;}`

[@priyanshshah6126]

because both the nodes exists in the tree is the criteria in leetcode

[@prachigupta2430]

Thanks for this much amazing content and explanation. Again very grateful 😊

[@ishaanchandak1258]

link of the question ?

[@deepakojha3216]

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...!!

[@takeUforward]

I promised if you give me 10k likes, you did not 🥲 Anyways will be up from Dec 1

[@PrinceKumar-el7ob]

@@takeUforward bhaiya thodi jldi november m hi upload krdo placement season hai december m 😿. like to bhaiya aa jayenge content hi aise hai 💓.

[@dipeshsaili4468]

@@takeUforward apne mera resume roast kardia pr purra nhi dekha :c

[@_PB03]

//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 ; } };

[@himanshuranjan8657]

Line 13 should be : if(root == NULL) return root ;

[@igaming_]

U can write return null or return root (both are correct)

[@prafuljohn15]

Striver bhai c++ pr chal nahi raha hai aapka code

[@iamnoob7593]

US

[@ishwaripednekar5164]

This is just outstanding

[@shivalikagupta3433]

Thank you so mcuh for all your hard work !!!

[@DevanshuAugusty]

tc = logn right?

[@only_for_fun1234r]

No, think of shew bst it will be o(n)

[@DevanshuAugusty]

@@only_for_fun1234r yes you are right . thanx

[@sammedpatil3907]

nice explanation....

[@SiddheshKukade]

thanks

[@player-te8tf]

striver runs java code in c++ mode (7:52) on leetcode, halke me mt lena god hai bro apna

[@deeyasings]

understood

[@UECAshutoshKumar]

Thank you sir

[@anonymous090]

Thank you Bhaiya

[@sayakbasak587]

thanks bhaiya

[@debugagrawal]

DSA God 😍🙌🚩🚀

[@alesblaze4745]

thanks mate!

[@venutalla5932]

Tq sir

[@roopeshn3301]

Understood

[@atifali3485]

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; } } }

[@bhaveshrathod9898]

Thanks for the video:)

[@abhishek__anand__]

Super

[@ajayypalsingh]

💚

[@BharatVaad]

great

[@rishabhgupta9846]

able to solve by myself

[@NikhilGupta-zo5jh]

UnderStood

[@piyushacharya7696]

// 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; } }

[@tejalsaraswat]

u r the besttt

[@aditya14-02]

Awesome code,video keep it uo

[@605_samikrdas4]

soooo goood trulyyy

[@suvanshmahajan5902]

"us"

[@dreamyme543]

Understood:)

[@theonlyisteve7261]

shit got real, nice1

[@ashutoshtripathi8257]

🔥🔥❤️

[@hitheshpk6030]

Understood

[@abhinanda7049]

understood

[@tech_wizard9315]

I am a DSA beginner,is your trees series enough to crack tech giant's like Microsoft linkedin level companies?

[@deepakojha3216]

hell,yes...!!

[@tanishkumar6682]

understood

[@tanmayjain5576]

Understood

[@adityapandey23]

Understood

[@Shivi32590]

understood