Lowest Common Ancestor of a Binary Tree | Leetcode 236 | Microsoft | Amazon | codestorywithMIK

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Thank you
#coding #helpajobseeker #easyrecipes
#interviewpreparation #interview_ds_algo #hinglish

[sanchitagarwal]

your explaination straight forwardly find its way to our brain !

[imbmali]

Excellent explanation. More power to you!

[maneetrajgupta]

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

[TalhaTabrez]

thank you mazhar!! helped me get the concept.. also inspiring me to think in the same way your brain functions

[ArjunSaxena-wlqs]

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

[shraban]

great explanation as always! Thanks for helping me out !

[rdrahuldhiman]

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.

[dayashankarlakhotia]

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

[mohakkapoor]

A good follow up would be how about if p or q is not present in the tree"

[ShikhaSehrawat-ms]

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

[gyandyan]

bool findPath(TreeNode* root, TreeNode* target, std::vector<TreeNode*>& 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* root, TreeNode* p, TreeNode* q) {
std::vector<TreeNode*> 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

[blackstargaming]

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

[nawazthezaifre]

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.

[NikhilSatyam]

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

[divyanshupant]

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q){
if(root == NULL) return NULL;
if(root == p || root== q) return root;
TreeNode* leftN = lca(root->left, p, q);
TreeNode* rightN = lca(root->right, p, q);
if(!leftN && !rightN) return root;
if(!leftN) return leftN;
if(!rightN) return rightN;
}

[priyankakataria]

Can you please give the iterative solution too

[kumkumslab]

Why memory Limit exceed on this test case Plzz reply

TreeNode* solve(TreeNode*root, int &s, int &e){
if(!root){
return NULL;
}
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<<temp->val<<" ";
string ans="";
string t="";
sol(temp, s, t, "");
// reverse(begin(t), end(t));
ans+=t;
t="";
sol2(temp, e, t, "");
ans+=t;
return ans;
}

[kusumjoshi]

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