Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

For example:

• If the tree is [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1, then the expected output is 3, because the LCA of nodes 5 and 1 is 3.
• If the tree is [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4, then the expected output is 5, because the LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
• If the tree is [1,2], p = 1, q = 2, then the expected output is 1.

Consider these constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

## Lowest Common Ancestor in a Binary Tree

This problem asks us to find the lowest common ancestor (LCA) of two given nodes in a binary tree.  The LCA is defined as the lowest node in the tree that has both input nodes as descendants (including the possibility that a node is a descendant of itself).

### Naive Solution (Brute Force)

A brute force approach would involve traversing the tree to find the paths from the root to each of the target nodes, `p` and `q`. Then, we can compare these paths to find the last common node, which will be the LCA.

However, this approach is not efficient and requires storing the paths, leading to higher space complexity.

### Optimal Solution (Recursive Approach)

A more efficient approach uses recursion. The idea is:

1.  If the current node is `null`, return `null`.
2.  If the current node is either `p` or `q`, return the current node.
3.  Recursively search the left and right subtrees for `p` and `q`.
4.  If both the left and right subtrees return non-null nodes, then the current node is the LCA.
5.  If only one subtree returns a non-null node, then the LCA is in that subtree.

```python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def lowestCommonAncestor(root, p, q):
    if not root:
        return None

    if root == p or root == q:
        return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    if left and right:
        return root
    elif left:
        return left
    else:
        return right

Here is an example binary tree visualized:

      3
     / \
    5   1
   / \ / \
  6  2 0  8
 / \       
7   4       

In the example above, if p = 5 and q = 1, then the function would recurse as follows:

1. lowestCommonAncestor(3, 5, 1)
2. left = lowestCommonAncestor(5, 5, 1) (returns 5)
3. right = lowestCommonAncestor(1, 5, 1) (returns 1)
4. Since both left and right are not None, return 3.

Thus, the LCA is 3.

Big(O) Runtime Analysis

The time complexity of this recursive approach is O(N), where N is the number of nodes in the binary tree. In the worst-case scenario, we might have to visit all nodes in the tree to find p and q. However, if p and q are close to the root, the algorithm might terminate earlier.

Big(O) Space Usage Analysis

The space complexity is O(H), where H is the height of the binary tree. This is due to the recursive call stack. In the worst-case scenario (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best-case scenario (balanced tree), H is log(N), resulting in O(log(N)) space complexity.

Edge Cases

1. Empty Tree: If the root is None, the function should return None.
2. p or q is the root: If either p or q is the root, the root is the LCA.
3. p and q are not in the tree: The problem statement guarantees that p and q will exist in the tree, so we don't need to handle this case explicitly. However, if we had to, we could add a check to verify that both p and q are found during the traversal. If either is not found, we can return None.
4. One node is a descendant of the other: If one node is a descendant of the other, the ancestor node is the LCA. The algorithm naturally handles this case.