Lowest Common Ancestor of a Binary Tree-(Microsoft, Amazon, Accolite...):Live Coding 🧑🏻‍💻

[@sanchitagarwal9651]

your explaination straight forwardly find its way to our brain !

[@codestorywithMIK]

Thank you so much 😇🙏

[@imbmali]

Excellent explanation. More power to you!

[@codestorywithMIK]

Thank you so much ❤️❤️❤️

[@shraban8508]

great explanation as always! Thanks for helping me out !

[@ArjunSaxena-wl3qs]

3:59 Thought to Try . . class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': def findAncestors(b) : q = deque([(root, [root])]) while q: for _ in range(len(q)): node, path = q.popleft() if node.val == b.val: return path if node.left: q.append((node.left, path + [node.left])) if node.right: q.append((node.right, path + [node.right])) pAncs = findAncestors(p) qAncs = findAncestors(q) lca = None for node_p, node_q in zip(pAncs, qAncs): if node_p == node_q: lca = node_p else: break return lca

[@anuppal3243]

Great explanation...

[@codestorywithMIK]

Thanks a lot Anup

[@maneetrajgupta]

sir, iske binary lifting wale approch pe bhi ek video bana do

[@rdrahuldhiman19]

Doubt: At 3.45, you said common ancestor of 4 is 5, but common is 5 and 3. Why we didn't consider 3, that is also the lowest one. Answer: Here we need to find lowest ancestor not based on the value of node, but based on the position, hence lowest is 5 and not 3, since 3 is lower in terms of it's value, but not in terms of position in the tree.

[@tanusingh5399]

here, we have to find the p and q common root node and in that case p itself is the root node and q is its child node. So In this case we have to return p node as the LCA.

[@ugcwithaddi]

Best explanation ❤

[@jaydeepjaydeep4924]

wow sir, great explanation (*****)

[@codestorywithMIK]

Thank you 😇❤️

[@VaishnaviSoni-n7x]

Ty bhaiya you are great

[@dayashankarlakhotia4943]

Class solution { Public TreeNode lowest common ancestors (TreeNode root,TreeNode p,TreeNode q){ if(root ==null || root ==p||root ==q) return root; TreeNode left =lowest common ancestors (root. left,p,q) TreeNode right =lowest common ancestors (root. right,p,q); return left ==null?right:right ==null?left:root

[@amanbalhara7365]

Nice explanation 😁

[@codestorywithMIK]

Thanks a lot Aman ❤️

[@ShikhaSehrawat-m5s]

Please include time and space complexity as well with all possible solutions.

[@codestorywithMIK]

Sure, in current videos, i add TC and SC

[@Ashutoshkumar-jx9wk]

Thanks 🙏

[@tutuimam3381]

Thanks a lot

[@priyankakataria7922]

Can you please give the iterative solution too

[@nawazthezaifre8870]

hello Sir ! can we apply one optimization in this code that i.e jab hame left and right dono hi not null mile to me further recursive call ko roke do. Just suppose hame left subTree se hi p and q mil gya then hame phir right subtree me jane ki kya zarorat hai. plz correct me if I'm wrong.

[@nawazthezaifre8870]

plz check the optimized code: /Optimized code class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == NULL) return NULL; if(root == p || root == q) return root; TreeNode* leftAns = lowestCommonAncestor(root->left, p, q); // Check if both p and q are found in the left subtree if(leftAns != NULL && leftAns != p && leftAns != q) return leftAns; TreeNode* rightAns = lowestCommonAncestor(root->right, p, q); if(leftAns != NULL && rightAns != NULL) return root; if(leftAns != NULL) return leftAns; return rightAns; } }; @codestorywithMIK

[@yogeshverma9267]

@@nawazthezaifre8870 leftAns != NULL && leftAns != p && leftAns != q -> This condition will always be False, either leftAns will be null (if both are in right), or it will be equal to p or q, and you have put (&&) comparison. This is not an optimization, rather an unnecessary check, it's always through the same route. The reason is we are not checking for both p and q anytime, if we find either of them we return.

[@saurabhKumar-hj6yp]

❤❤

[@NikhilSatyam]

bhai p = 5 and q =4 me LCS to 3 hona chahiye na kyunki wo common v hai aur lowest v

[@sinnohperson8813]

Lowest matlab the most recent , value nahi.

[@closer9689]

Not 3 , It will be 5 because Question me LCS ki definition me likha hai ki ek node khud ka bhi LCS hoga so , Path of 5 -> 3 5 4 -> 3 5 2 4 Now forget about LCS . Just see which is the lowest common node between these two path....and it is 5. Note that 3 is above 5 it is not the lowest. ALSO here lowest means the level of node and not its value. Level Wise Lowest.

[@blackstargaming3678]

bhai ek chota sa doubt he agar hum leftN , rightN nikal rahe hain , phir check kar rahe hain ki agar dono null nhi hua toh return root kardo , phir ham kuyn if(root==p||root==q) retrun root likh rahe hain ? woh samaj nhi aya

[@Memerluffy]

2:08

[@basujain8928]

bhai tum famous kyo nhi ho

[@gyandyan]

bool findPath(TreeNode* root, TreeNode* target, std::vector& path) { if (!root) return false; path.push_back(root); if (root == target) return true; if ((root->left && findPath(root->left, target, path)) || (root->right && findPath(root->right, target, path))) { return true; } path.pop_back(); return false; } // Function to find the LCA using the paths stored in vectors. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { std::vector path1, path2; // Find paths from the root to p and q. if (!findPath(root, p, path1) || !findPath(root, q, path2)) { return nullptr; } // Compare the paths to get the first different value. int i; for (i = 0; i < path1.size() && i < path2.size(); ++i) { if (path1[i] != path2[i]) break; } // Return the last common node. return path1[i-1]; } //Brute force sol

[@kusumjoshi4613]

Please reduce the adds amount a bit if possible. In a single video I am seeing more than 7-8 adds, its irritating while I am trying to focus on the content

[@codestorywithMIK]

So sorry for the inconvenience. Unfortunately ads are now controlled by KZbin entirely and we can’t control the number of ads in a video. Feel free to use Adblocker. That’s totally fine. I don’t any inconvenience to you guys ❤️

[@kumkumslab5811]

Why memory Limit exceed on this test case Plzz reply TreeNode* solve(TreeNode*root,int &s,int &e){ if(!root){ return NULL; } if(root->val==s||root->val==e){return root;} TreeNode *l=solve(root->left,s,e); TreeNode *r=solve(root->right,s,e); if(l!=NULL && r!=NULL){ return root; } if(l!=NULL)return l; else return r; } void sol(TreeNode*root,int &s,string &t,string temp){ if(!root){ return ; } if(root->val==s){ t=temp; return ; } sol(root->left,s,t,temp+"U"); sol(root->right,s,t,temp+"U"); } void sol2(TreeNode*root,int &s,string &t,string temp){ if(!root){ return ; } if(root->val==s){ t=temp; return ; } sol2(root->right,s,t,temp+"R"); sol2(root->left,s,t,temp+"L"); } string getDirections(TreeNode* root, int s, int e) { TreeNode *temp=solve(root,s,e); // cout