Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        return left ? left : right;
    }
};
      

// 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 && right != null) return root;
        return left != null ? left : right;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left ? left : right;
};
      

Problem Description

You are given the root node root of a binary tree and two distinct nodes p and q within that tree. Your task is to find the lowest common ancestor (LCA) of nodes p and q.

The lowest common ancestor of two nodes p and q is defined as the deepest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

• All node values are unique.
• Both p and q are guaranteed to exist in the tree.
• There is exactly one lowest common ancestor for p and q.

Thought Process

At first glance, the problem asks us to identify the lowest node in a binary tree that is an ancestor to both p and q. A brute-force approach might be to find the paths from the root to p and q, then compare the paths to find the last common node.

However, this approach requires extra space to store the paths and extra time to compare them. Is there a way to do this more efficiently, perhaps in a single traversal?

If we think recursively, we can ask: at any node, does its left or right subtree contain p or q? If both subtrees return a non-null result, then the current node must be the LCA. This insight leads us toward a divide-and-conquer strategy, which is both elegant and efficient.

Solution Approach

• Step 1: Use recursion to traverse the tree starting from the root.
• Step 2: For each node, check:
  • If the node is null, return null (base case).
  • If the node is either p or q, return the node itself (since a node is a descendant of itself).
• Step 3: Recursively search the left and right subtrees for p and q.
• Step 4: After recursion:
  • If both left and right recursive calls return non-null nodes, it means p and q are found in different subtrees, so the current node is their LCA.
  • If only one side returns non-null, propagate that non-null value up the recursion stack.
  • If both sides return null, return null.
• Step 5: The recursion will eventually return the LCA node to the caller.

This approach is efficient because it only visits each node once, and does not require storing extra paths or parent pointers.

Example Walkthrough

Consider the following binary tree:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
  

Suppose p = 5 and q = 1. Let's trace the steps:

1. Start at root 3. It's not p or q.
2. Recurse left to 5. This matches p, so return 5 up.
3. Recurse right to 1. This matches q, so return 1 up.
4. At root 3, both left and right returned non-null (5 and 1), so 3 is their LCA.

If p = 5 and q = 4, the recursion would find both in the left subtree, and thus the LCA would be 5 itself.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N) to find each path, so O(N) for both paths (where N is the number of nodes), plus O(N) to compare them.
  • Space: O(N) for storing each path.
• Optimized recursive approach (current):
  • Time: O(N), since we visit each node at most once.
  • Space: O(H), where H is the height of the tree, due to the recursion stack. For a balanced tree, H = log N; for a skewed tree, H = N.

Summary

The lowest common ancestor problem in a binary tree can be solved efficiently using a simple recursive approach. By leveraging the properties of recursion and the definition of ancestry, we avoid unnecessary storage or repeated traversals. The key insight is that if p and q are found in different subtrees of a node, that node is their LCA. This makes the solution both elegant and optimal in terms of time and space.