🎨Now live: Try our Free AI Image Generation Feature

Description
The problem involves finding the lowest common ancestor (LCA) of two nodes p
and q
in a binary tree. The LCA is defined as the lowest node in the tree that has both p
and q
as descendants.
Intuition
To find the LCA of nodes p
and q
:
- If the current node is
None
or equal to eitherp
orq
, it is returned as a potential LCA. - Recursively traverse left and right subtrees to find nodes
p
andq
. - If both nodes are found in different subtrees, then the current node is the LCA.
- If both nodes are found in the same subtree, the LCA lies in that subtree.
Approach
- Implement a recursive function that checks if the current node is
None
or equals eitherp
orq
. - Recursively search in the left and right subtrees for nodes
p
andq
. - If both nodes are found in different subtrees of a node, that node is the LCA.
- If both nodes are found in the same subtree, recurse further to find the LCA.
Complexity
Time Complexity:
O(n), where n is the number of nodes in the binary tree. Each node is visited once.
Space Complexity:
O(n) in the worst case due to recursion stack space, where n is the height of the tree (for a skewed tree).
Code
C++
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) {
return root;
}
TreeNode* resL = lowestCommonAncestor(root->left, p, q);
TreeNode* resR = lowestCommonAncestor(root->right, p, q);
if (resL && resR) {
return root;
} else if (resL) {
return resL;
} else {
return resR;
}
}
};
Python
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# Base case: if root is None or root is either p or q, return root
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# If both left and right subtrees have found nodes, then root is the LCA
if left and right:
return root
return left if left else right
Java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || 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;
} else if (left != null) {
return left;
} else {
return right;
}
}
}
JavaScript
function lowestCommonAncestor(root, p, q)
{
if (!root || root === p || root === q) return root;
var resL = lowestCommonAncestor(root.left, p, q);
var resR = lowestCommonAncestor(root.right, p, q);
return (resL && resR) ? root : (resL || resR);
}