Lowest Common Ancestor in a Binary Tree

Problem Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Brute Force Approach

One straightforward but inefficient approach is to traverse the tree to find the paths from the root to both nodes p and q. Once these paths are found, we can compare them from the root down until the paths diverge. The last common node in both paths is the LCA.

• Time Complexity: O(N), where N is the number of nodes in the tree in the best case (p and q are close to the root), but can be O(N^2) in the worst case if finding the paths involves traversing most of the tree multiple times.
• Space Complexity: O(N) to store the paths from the root to the nodes p and q.

Optimal Approach (Recursive)

A more efficient solution utilizes recursion. The idea is as follows:

1. If the root is null, return null.
2. If the root is equal to p or q, return the root.
3. Recursively search for p and q in the left and right subtrees.
4. If both the left and right subtrees return a non-null node, it means p and q are found in different subtrees. Therefore, the current root is the LCA.
5. If only one of the subtrees returns a non-null node, it means both p and q are in that subtree. Return the non-null node.

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because, in the worst-case scenario, we may need to visit all nodes.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (balanced tree), H would be log(N), resulting in O(log(N)) space complexity.

Edge Cases

• If either p or q is the root, the root is the LCA.
• If p or q do not exist in the tree, the algorithm will still return a node, but it might not be a valid LCA. The problem statement guarantees that both p and q will exist.
• If the tree is empty, the problem statement doesn't apply as it requires at least two nodes.

Code (Java)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        }

        return (left != null) ? left : right;
    }
}