236. Lowest Common Ancestor of a Binary Tree

Description

The problem involves finding the lowest common ancestor (LCA) of two nodes p and q in a binary tree. The LCA is defined as the lowest node in the tree that has both p and q as descendants.

Intuition

To find the LCA of nodes p and q:

• If the current node is None or equal to either p or q, it is returned as a potential LCA.
• Recursively traverse left and right subtrees to find nodes p and q.
• If both nodes are found in different subtrees, then the current node is the LCA.
• If both nodes are found in the same subtree, the LCA lies in that subtree.

Approach

1. Implement a recursive function that checks if the current node is None or equals either p or q.
2. Recursively search in the left and right subtrees for nodes p and q.
3. If both nodes are found in different subtrees of a node, that node is the LCA.
4. If both nodes are found in the same subtree, recurse further to find the LCA.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the binary tree. Each node is visited once.

Space Complexity:

O(n) in the worst case due to recursion stack space, where n is the height of the tree (for a skewed tree).

Code

C++

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

Python

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Base case: if root is None or root is either p or q, return root
        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 both left and right subtrees have found nodes, then root is the LCA
        if left and right:
            return root
        return left if left else right

Java

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;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

JavaScript

function lowestCommonAncestor(root, p, q) 
{
    if (!root || root === p || root === q) return root;
    var resL = lowestCommonAncestor(root.left, p, q);
    var resR = lowestCommonAncestor(root.right, p, q);
    return (resL && resR) ? root : (resL || resR);
}