Lowest Common Ancestor

Find the lowest common ancestor of two nodes in a binary tree.

Language Selection

Choose your preferred programming language

Showing: Python

Lowest Common Ancestor

Problem Statement

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).”

Examples

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.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1
Explanation: The LCA of nodes 1 and 2 is 1.

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Approach 1: Recursive DFS (Optimal)

Algorithm

Use recursion to find the lowest common ancestor by checking if nodes are in left or right subtrees.

Steps:

  1. Base case: if current node is null, return null
  2. If current node is p or q, return current node
  3. Recursively search left and right subtrees
  4. If both subtrees return non-null, current node is LCA
  5. Return non-null result from either subtree

Implementation

Python:

def lowestCommonAncestor(root, p, q):
    """
    Find lowest common ancestor using recursive DFS
    Time: O(n)
    Space: O(h) where h is height of tree
    """
    if not root:
        return None
    
    # If current node is p or q, return it
    if root == p or root == q:
        return root
    
    # Search in left and right subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # If both subtrees return non-null, current node is LCA
    if left and right:
        return root
    
    # Return non-null result from either subtree
    return left or right

Java:

class Solution {
    /**
     * Find lowest common ancestor using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        
        // If current node is p or q, return it
        if (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 subtrees return non-null, current node is LCA
        if (left != null && right != null) {
            return root;
        }
        
        // Return non-null result from either subtree
        return left != null ? left : right;
    }
}

Go:

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    /**
     * Find lowest common ancestor using recursive DFS
     * Time: O(n)
     * Space: O(h) where h is height of tree
     */
    if root == nil {
        return nil
    }
    
    // If current node is p or q, return it
    if root == p || root == q {
        return root
    }
    
    // Search in left and right subtrees
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    
    // If both subtrees return non-null, current node is LCA
    if left != nil && right != nil {
        return root
    }
    
    // Return non-null result from either subtree
    if left != nil {
        return left
    }
    return right
}

JavaScript:

/**
 * Find lowest common ancestor using recursive DFS
 * Time: O(n)
 * Space: O(h) where h is height of tree
 */
function lowestCommonAncestor(root, p, q) {
    if (!root) {
        return null;
    }
    
    // If current node is p or q, return it
    if (root === p || root === q) {
        return root;
    }
    
    // Search in left and right subtrees
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    // If both subtrees return non-null, current node is LCA
    if (left && right) {
        return root;
    }
    
    // Return non-null result from either subtree
    return left || right;
}

C#:

public class Solution {
    /// <summary>
    /// Find lowest common ancestor using recursive DFS
    /// Time: O(n)
    /// Space: O(h) where h is height of tree
    /// </summary>
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        
        // If current node is p or q, return it
        if (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 subtrees return non-null, current node is LCA
        if (left != null && right != null) {
            return root;
        }
        
        // Return non-null result from either subtree
        return left ?? right;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node exactly once
  • Space Complexity: O(h) - Recursion stack depth equals tree height

Key Insights

  1. LCA Property: LCA is the lowest node that has both nodes as descendants
  2. Recursive Approach: Most elegant and efficient solution
  3. Path Finding: Alternative approach using path comparison
  4. Node Identity: Check node identity, not values
  5. Early Termination: Return as soon as LCA is found

Edge Cases

  1. One Node is Ancestor: One node is ancestor of the other
  2. Root is LCA: Root is the lowest common ancestor
  3. Same Node: Both nodes are the same (shouldn’t happen per constraints)
  4. Skewed Tree: Handle left-skewed or right-skewed trees
  5. Large Tree: Handle trees with many nodes

Test Cases

def test_lowestCommonAncestor():
    # Test case 1: Normal case
    root1 = TreeNode(3)
    root1.left = TreeNode(5)
    root1.right = TreeNode(1)
    root1.left.left = TreeNode(6)
    root1.left.right = TreeNode(2)
    root1.right.left = TreeNode(0)
    root1.right.right = TreeNode(8)
    root1.left.right.left = TreeNode(7)
    root1.left.right.right = TreeNode(4)
    
    p1 = root1.left  # 5
    q1 = root1.right  # 1
    result1 = lowestCommonAncestor(root1, p1, q1)
    assert result1 == root1  # 3
    
    # Test case 2: One node is ancestor
    p2 = root1.left  # 5
    q2 = root1.left.right.right  # 4
    result2 = lowestCommonAncestor(root1, p2, q2)
    assert result2 == root1.left  # 5
    
    # Test case 3: Root is LCA
    root3 = TreeNode(1)
    root3.left = TreeNode(2)
    p3 = root3  # 1
    q3 = root3.left  # 2
    result3 = lowestCommonAncestor(root3, p3, q3)
    assert result3 == root3  # 1
    
    print("All tests passed!")

test_lowestCommonAncestor()

Follow-up Questions

  1. LCA in BST: Find LCA in binary search tree?
  2. LCA with Parent Pointers: Use parent pointers for optimization?
  3. LCA of Multiple Nodes: Find LCA of more than two nodes?
  4. LCA with Distance: Find LCA and distance to both nodes?
  5. LCA in N-ary Tree: Handle n-ary trees?

Common Mistakes

  1. Value Comparison: Comparing node values instead of node identity
  2. Missing Base Cases: Not handling null nodes properly
  3. Wrong Return Logic: Not handling the case where both subtrees return non-null
  4. Path Finding Errors: Incorrect path construction or comparison
  5. Edge Case Handling: Not handling one node being ancestor of the other

Interview Tips

  1. Start with Recursion: Most intuitive and efficient approach
  2. Explain LCA Concept: Show understanding of lowest common ancestor
  3. Handle Edge Cases: Mention one node being ancestor of the other
  4. Discuss Trade-offs: Compare recursive vs path finding approaches
  5. Follow-up Ready: Be prepared for BST and parent pointer variations

Concept Explanations

Lowest Common Ancestor: The LCA of two nodes is the lowest node in the tree that has both nodes as descendants. A node can be a descendant of itself.

Recursive Approach: We recursively search for both nodes in the left and right subtrees. If both subtrees return non-null results, the current node is the LCA. If only one subtree returns a non-null result, that result is the LCA.

Path Finding Approach: We find the path from root to each node, then compare the paths to find the last common node. This approach is more intuitive but less efficient.

Why Recursion Works: The problem has a recursive structure - if we can find the LCA in a subtree, we can determine the LCA for the entire tree.

Node Identity: We check node identity (reference equality) rather than node values, since nodes can have the same value but be different nodes.

Early Termination: The recursive approach can terminate early when it finds one of the target nodes, making it more efficient than the path finding approach.