Python Program to Find the Lowest Common Ancestor in a Binary Tree

This program identifies the lowest common ancestor (LCA) of two given nodes in a binary tree. The LCA is the deepest node that has both nodes as its descendants. The algorithm employs a recursive depth-first search to navigate the tree and determine the LCA.

class TreeNode:
    """A node in a binary tree."""
    def __init__(self, x):
        """
        Initialize a tree node with a value.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """Solution to find the lowest common ancestor in a binary tree."""
    
    def lowestCommonAncestor(self, root, p, q):
        """
        Find the lowest common ancestor of two nodes p and q.
        
        :param root: TreeNode, the root of the binary tree
        :param p: TreeNode, first node
        :param q: TreeNode, second node
        :return: TreeNode, the lowest common ancestor of nodes p and q
        """
        if root is None 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

# Example Usage
if __name__ == "__main__":
    # Create a binary tree
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)
    
    # Nodes to find the LCA
    p = root.left  # Node 5
    q = root.left.right.right  # Node 4

    # Solution instance
    sol = Solution()
    
    # Finding the LCA
    lca = sol.lowestCommonAncestor(root, p, q)
    print("Lowest Common Ancestor:", lca.val)

The program defines a class TreeNode for the binary tree nodes and a class Solution that contains the method lowestCommonAncestor. This method uses recursion to traverse the tree and identifies the LCA based on whether each subtree contains one of the two nodes. If both the left and right subtree return non-null values, the current node is the LCA. Otherwise, the non-null return value from either subtree will be the LCA.