Lowest Common Ancestor II

XXX. Lowest Common Ancestor of a Binary Tree

Binary Tree

Recursion

Depth-First Search

Problem Statement:

Given a binary tree and two nodes, p and q, find their lowest common ancestor (LCA). The LCA of two nodes is the lowest node in the tree that has both p and q as descendants.

If either p or q does not exist in the tree, return null.

Algorithm:

1. Traverse the tree using depth-first search (DFS).
2. For each node:
   • Check the left and right subtrees for the presence of p or q.
   • If the current node is equal to p or q, update the respective flag (found_p or found_q).
   • If both left and right subtrees return non-null, the current node is the LCA.
3. After traversing, check if both p and q are found in the tree. If not, return null.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree (due to recursion stack).

Java Implementation:

class Solution {
    // Flags to track if p and q are found in the tree
    private boolean found_p = false, found_q = false;

    // Helper function to recursively find the lowest common ancestor
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null; // Base case: null node

        // Recur for the left and right subtrees
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);

        // If the current node is p, update the found_p flag
        if (root == p) {
            found_p = true;
            return root;
        }

        // If the current node is q, update the found_q flag
        if (root == q) {
            found_q = true;
            return root;
        }

        // If both left and right subtrees contain p or q, the current node is the LCA
        if (left != null && right != null) return root;

        // Otherwise, return the non-null child (or null if both are null)
        return left == null ? right : left;
    }

    // Main function to find the LCA of p and q
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = lca(root, p, q);

        // Check if both p and q were found
        if (found_p && found_q) return res;

        return null; // Return null if either p or q is not found
    }
}
                

Python Implementation:

class Solution:
    def __init__(self):
        self.found_p = False
        self.found_q = False

    def lca(self, root, p, q):
        if not root:
            return None

        # Recur for the left and right subtrees
        left = self.lca(root.left, p, q)
        right = self.lca(root.right, p, q)

        # If the current node is p, update the found_p flag
        if root == p:
            self.found_p = True
            return root

        # If the current node is q, update the found_q flag
        if root == q:
            self.found_q = True
            return root

        # If both left and right subtrees contain p or q, the current node is the LCA
        if left and right:
            return root

        # Otherwise, return the non-null child (or None if both are None)
        return left if left else right

    def lowestCommonAncestor(self, root, p, q):
        res = self.lca(root, p, q)

        # Check if both p and q were found
        if self.found_p and self.found_q:
            return res

        return None