Lowest Common Ancestor

medium · tree traversal

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"

Starter code

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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  2. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  3. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.