Lowest Common Ancestor of a Binary Tree
MedPrompt
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).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 105]. -109 <= Node.val <= 109- All
Node.valare unique. p != qpandqwill exist in the tree.
Approaches
2 approaches with complexity analysis and trade-offs.
Find paths from root to both nodes p and q, then compare the paths to find the last common node.
Algorithm
- Create two lists to store paths from root to p and q
- Use DFS to find path from root to p
- Use DFS to find path from root to q
- Compare both paths to find the last common node
- Return the last common node as LCA
Walkthrough
This approach involves two steps:
- First, we find the path from root to both nodes p and q by doing a DFS traversal and storing the paths.
- Then we compare both paths to find the last common node which will be our LCA.
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { List<TreeNode> path1 = new ArrayList<>(); List<TreeNode> path2 = new ArrayList<>(); findPath(root, p, path1); findPath(root, q, path2); TreeNode lca = null; int i = 0; while (i < path1.size() && i < path2.size()) { if (path1.get(i) == path2.get(i)) { lca = path1.get(i); } i++; } return lca; } private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) { if (root == null) return false; path.add(root); if (root == node) return true; if (findPath(root.left, node, path) || findPath(root.right, node, path)) { return true; } path.remove(path.size() - 1); return false; }}Complexity
Time
O(N) where N is the number of nodes in the tree. We need to traverse the tree twice to find paths.
Space
O(H) where H is the height of the tree, needed to store the paths
Trade-offs
Pros
Easy to understand and implement
Works for any binary tree
No extra space needed except for storing paths
Cons
Requires two tree traversals
Needs extra space to store paths
Not very efficient for large trees
Solutions
Solution
/** * 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 || root == p || root == q ) return root ; TreeNode left = lowestCommonAncestor ( root . left , p , q ); TreeNode right = lowestCommonAncestor ( root . right , p , q ); if ( left == null ) return right ; if ( right == null ) return left ; return root ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.