Lowest Common Ancestor of a Binary Tree-(Microsoft, Amazon, Accolite...):Live Coding 🧑🏻💻
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- In this video we will try to solve “Lowest Common Ancestor of a Binary Tree”.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Lowest Common Ancestor of a Binary Tree
Company Tags : Accolite, Amazon, American Express, Expedia, MakeMyTrip, Microsoft, Payu, Snapdeal, Times Internet, Twitter
Leetcode Link : leetcode.com/p...
My solutions on Github : github.com/MAZ...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Thank you
#coding #helpajobseeker #easyrecipes
#interviewpreparation #interview_ds_algo #hinglish
your explaination straight forwardly find its way to our brain !
Thank you so much 😇🙏
Excellent explanation. More power to you!
Thank you so much ❤️❤️❤️
great explanation as always! Thanks for helping me out !
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.
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.
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
Please include time and space complexity as well with all possible solutions.
Sure, in current videos, i add TC and SC
Great explanation...
Thanks a lot Anup
Ty bhaiya you are great
sir, iske binary lifting wale approch pe bhi ek video bana do
Best explanation ❤
Nice explanation 😁
Thanks a lot Aman ❤️
wow sir, great explanation (*****)
Thank you 😇❤️
bhai p = 5 and q =4 me LCS to 3 hona chahiye na kyunki wo common v hai aur lowest v
Lowest matlab the most recent , value nahi.
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.
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
Thanks 🙏
Can you please give the iterative solution too
❤❤
Thanks a lot
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.
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
@@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.
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
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
bhai tum famous kyo nhi ho
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
2:08
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
So sorry for the inconvenience. Unfortunately ads are now controlled by TH-cam 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 ❤️