Lowest Common Ancestor of a Binary Tree

To solve the Lowest Common Ancestor problem for a general binary tree, I would use a post-order traversal approach via recursion. First, I'd clarify if this is a BST or a standard binary tree; assuming it's a standard tree, we cannot rely on value ordering. The core logic involves checking three conditions at each node: if the current node matches p or q, we return it. Then, we recursively search the left and right subtrees. If both recursive calls return non-null values, it means p and q are found in different subtrees, making the current node the lowest common ancestor. If only one side returns a non-null value, that value propagates up, indicating both nodes lie in that subtree. For example, in a tree rooted at 3 with children 5 and 1, searching for 5 and 1 would find 5 in the left branch and 1 in the right. Since both branches return valid nodes, 3 is identified as the LCA. This approach ensures we visit each node exactly once, resulting in O(n) time complexity. Space complexity depends on the tree height, O(h), due to the recursion stack. I would also add a check to ensure p and q actually exist in the tree if the problem statement implies they might be missing, though typically LeetCode-style questions guarantee existence. This method is efficient, readable, and handles all structural variations of binary trees effectively.