236. Lowest Common Ancestor of a Binary Tree Leetcode Solution
Lowest Common Ancestor of a Binary Tree Leetcode Problem :
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Lowest Common Ancestor of a Binary Tree Leetcode Solution :
Constraints :
- The number of nodes in the tree is in the range [2, 105].
- -109 <= Node.val <= 109
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
Example 1:
- Input: root = [1,2], p = 1, q = 2
- Output: 1
Approach :
The function lowestCommonAncestor takes in three parameters: the root of a binary tree (root) and two nodes of the binary tree (p and q).
The first if statement checks if the root is None or if it is equal to either p or q. If either of these conditions is true, it means that we have found one of the nodes we are looking for, and we return the root.
Next, we recursively call the lowestCommonAncestor function on the left and right subtrees of the root, passing in the same nodes p and q. We store the results of these recursive calls in variables l and r, respectively.
The second if statement checks if both l and r are not None. If this condition is true, it means that we have found both p and q in different subtrees of the current root, and therefore the current root is the lowest common ancestor. We return the current root.
If the second if statement is not satisfied, we return either l or r, depending on which one is not None. This is because if only one of l and r is not None, it means that the other node is not in the subtree of the current root, so we return the node that is in the subtree.
If none of the previous conditions is satisfied, it means that both l and r are None, so we return None. This happens when we have reached the end of a branch of the binary tree without finding either p or q.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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* l = lowestCommonAncestor(root->left,p,q);
TreeNode* r = lowestCommonAncestor(root->right,p,q);
if(l&&r)return root;
if(l)return l;
if(r)return r;
return NULL;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
if(root == null) return null;
if(root == p || root == q) return root;
TreeNode left =lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null) return root;
return left == null? right: left;
}
}
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if l and r:
return root
return l or rGet over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment