236. Lowest Common Ancestor of a Binary Tree – Leetcode Solutions

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 according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

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 root is None or root == p or root == q:
            return root
        
        # Recursively search for p and q in the left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)   # Search in the left subtree
        right = self.lowestCommonAncestor(root.right, p, q) # Search in the right subtree
        
        # If both left and right are non-null, p and q are in different subtrees,
        # so the current root is their lowest common ancestor
        if left and right:
            return root
        
        # If only one side (either left or right) has returned a node,
        # it means both p and q are in that subtree.
        # So return the non-null node (either left or right).
        return left if left else right

var lowestCommonAncestor = function(root, p, q) {
    // Base case: if root is null, or root is either p or q, return root
    if (root === null || root === p || root === q) {
        return root;
    }

    // Recur for the left and right subtrees
    const left = lowestCommonAncestor(root.left, p, q);  // Search in left subtree
    const right = lowestCommonAncestor(root.right, p, q); // Search in right subtree

    // If both left and right are non-null, this means p and q are in different subtrees,
    // so the current node is the lowest common ancestor
    if (left !== null && right !== null) {
        return root;
    }

    // Otherwise, return the non-null value (if either left or right is non-null)
    return left !== null ? left : right;
};

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null, or root is either p or q, return root
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recur for the left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);  // Search in left subtree
        TreeNode right = lowestCommonAncestor(root.right, p, q); // Search in right subtree

        // If both left and right are non-null, p and q are in different subtrees,
        // so the current node is the lowest common ancestor
        if (left != null && right != null) {
            return root;
        }

        // Otherwise, return the non-null value (either left or right)
        return (left != null) ? left : right;
    }
}

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: if root is null or root is either p or q, return root
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // Recursively search in the left subtree
        TreeNode* left = lowestCommonAncestor(root->left, p, q);

        // Recursively search in the right subtree
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // If both left and right are non-null, p and q are in different subtrees,
        // so the current root is their lowest common ancestor
        if (left != nullptr && right != nullptr) {
            return root;
        }

        // If only one of left or right is non-null, return that node
        // This means both p and q are in the same subtree
        return left != nullptr ? left : right;
    }
};