Lowest Common Ancestor of a Binary Tree

Question

## Problem

Given a binary tree and two nodes `p` and `q`, return their **Lowest Common Ancestor (LCA)**.

The LCA is the deepest node that has both `p` and `q` as descendants (a node can be a descendant of itself).

## Example
```
      3
     / \
    5   1
   / \ / \
  6  2 0  8
LCA(5, 1) = 3
LCA(5, 6) = 5
```

## Follow-up variants asked at Microsoft
1. LCA in a Binary **Search** Tree (can you do it without recursion?)
2. LCA when parent pointers are available
3. LCA with multiple query pairs — how do you preprocess for O(log n) per query?