leetcode-236 Lowest Common Ancestor of a Binary Tree

# Given a binary tree, find the lowest common ancestor (LCA) of two given nodes.
# The LCA is defined as the lowest node that has both p and q as descendants
# (where we allow a node to be a descendant of itself).
#
# 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.
#
# Constraints:
# The number of nodes in the tree is in the range [2, 10^5].
# All Node.val are unique.
# p != q

# 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: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # Base case: if root is None or root is one of p or q
        if not root or root == p or root == q:
            return root

        # Search in left and right subtrees
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        # If both left and right are non-null, p and q are in different subtrees
        # Current root is the LCA
        if left and right:
            return root

        # If only one side is non-null, return that side
        # (both nodes are in that subtree, or only one node found so far)
        return left if left else right

# Time Complexity: O(n) - visit each node once in worst case
# Space Complexity: O(h) - recursion stack where h is tree height
#
# Key Insight: The first node where left and right subtree searches
# both return non-null values is the LCA