LeetCode 1650: Lowest Common Ancestor of a Binary Tree III

Explanation:

To find the lowest common ancestor of two nodes in a binary tree, we can use a recursive approach. We start from the root and traverse the tree recursively. At each node, we check if the current node is either of the two given nodes. If it is, we return the current node as a potential common ancestor. If the current node is not either of the two nodes, we recursively search the left and right subtrees.

If both left and right subtrees return a non-null value (i.e., they found one of the nodes), then the current node is the lowest common ancestor. If only one subtree returns a non-null value, then that subtree's result is the lowest common ancestor.

Algorithm:

1. Start from the root node.
2. If the current node is null or is either of the given nodes, return the current node.
3. Recursively search the left and right subtrees.
4. If both subtrees return non-null values, the current node is the lowest common ancestor.
5. If only one subtree returns a non-null value, return that value.

Time Complexity: O(n) - where n is the number of nodes in the binary tree. Space Complexity: O(h) - where h is the height of the binary tree.

: :

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        if (p == null || q == null) {
            return null;
        }
        
        Node a = p, b = q;
        while (a != b) {
            a = a == null ? q : a.parent;
            b = b == null ? p : b.parent;
        }
        
        return a;
    }
}