Lowest Common Ancestor

nodes maps unique string node IDs to [left_id_or_None, right_id_or_None]. It describes a valid binary tree rooted at root (which may be None). Given p and q IDs, return their lowest common ancestor ID, or None if either is not reachable from root. An ancestor may be the node itself, and p may equal q. Build parent links or traverse the tree; node identity is the ID, not a value. There are at most 100 nodes. Examples (JSON; null means Python None): Input: {"nodes": {"a": ["b", "c"], "b": ["d", null], "c": [null, null], "d": [null, null]}, "root": "a", "p": "d", "q": "c"} Output: "a" Input: {"nodes": {"a": ["b", null], "b": [null, null]}, "root": "a", "p": "a", "q": "b"} Output: "a"

def lowest_common_ancestor(nodes: dict, root: str | None, p: str, q: str) -> str | None:
    """Find the deepest shared ancestor, requiring both nodes to exist."""
    pass