Problem
Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA).The lowest common ancestor is the deepest node in the tree that has both p and q as descendants. A node can also be considered a descendant of itself.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 1
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
Output
3 Solution
This solution uses Depth-First Search (DFS) with recursion to search for both p and q throughout the tree. For every node, we recursively search its left and right subtrees.If the current node is
null, there is no target node in that path, so null is returned. If the current node is either p or q, that node is returned to its parent.
After searching both subtrees, there are two important cases. If both the left and right recursive calls return a non-null node, it means one target was found in the left subtree and the other was found in the right subtree. Therefore, the current node is the lowest common ancestor.
If only one side returns a non-null node, that result is passed upward because both target nodes may still be located further down in the same subtree, or one of the target nodes may itself be the ancestor of the other.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// No target found.
if (root == null) {
return null;
}
// Found one of the target nodes.
if (root == p || root == q) {
return root;
}
// Search both subtrees.
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Targets found on both sides.
if (left != null && right != null) {
return root;
}
// Return the found node to the parent recursive call.
return left != null ? left : right;
}
Complexity
In the worst case, every node in the binary tree may be visited, resulting in a time complexity ofO(n).
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.