Lowest Common Ancestor of a Binary Tree

Binary Tree Zigzag Level Order Traversal

Balanced Binary Tree

Find the lowest shared ancestor of two values in a general binary tree.

Given the `root` of a binary tree and two integer values `p` and `q` that are guaranteed to exist in the tree, return the value of their lowest common ancestor. A node is the lowest common ancestor when it is the deepest node that has both target values in its subtree (where a node can be a descendant of itself).

**Input / output**
- Input: `root: TreeNode`, `p: int`, `q: int` (`root` is provided in tests as a LeetCode-style level-order array such as `[3,5,1,6,2,0,8,null,null,7,4]`)
- Output: `int` — the value of the lowest common ancestor

## Examples
```json
Input: {"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":1}
Output: 3
```

```json
Input: {"root":[3,5,1,6,2,0,8,null,null,7,4],"p":5,"q":4}
Output: 5
```

## Constraints
- 2 <= number of nodes <= 100000
- All node values are unique
- `p` and `q` are different values that both exist in the tree

## Follow-up
Can you solve it with a single DFS that returns the matching node from each subtree and detects the first split point without storing parent pointers?

The key pattern is: post-order DFS bubbles target hits upward, and the first node where left and right searches both succeed is the LCA. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n) — in the worst case you may visit every node once. Space: O(h) for the recursion stack, where `h` is the tree height (O(n) in the worst skewed case).

All 7 languages below implement the same recursive LCA traversal for a general binary tree while taking `p` and `q` as raw integer values.