Lowest Common Ancestor

236.Lowest Common Ancestor of a Binary Tree

Tree

Recursion

Depth First Search

Problem Statement:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA is defined as the lowest node in the tree that has both nodes as descendants (where we allow a node to be a descendant of itself).

Example:

Input:

root = [3,5,1,6,2,0,8], p = 5, q = 1

→

Output:

3

Algorithm:

1. Use DFS to traverse tree
2. Return if root is null or matches p/q
3. Search left and right subtrees
4. Return common ancestor if found

Complexity:

Time: O(n) | Space: O(h) where h is height of tree

Java Solution:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // Base case: if root is null or matches either node
    if(root == null || root == p || root == q)  
        return root;
    
    // Search in left and right subtrees
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // If both left and right found, this is LCA
    if(left != null && right != null)   
        return root;
    
    // Return non-null node
    return left != null ? left : right;
}

Python Solution:

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # Base case
    if not root or root == p or root == q:
        return root
        
    # Search subtrees
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    
    # Both nodes found
    if left and right:
        return root
        
    # Return non-null result
    return left if left else right

C++ Solution:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case
        if(!root || root == p || root == q)
            return root;
            
        // Search subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // Both found - this is LCA
        if(left && right)
            return root;
            
        // Return non-null node
        return left ? left : right;
    }
};