Constraints

• 1 <= number of nodes <= 10^5
• The tree may be highly unbalanced
• Node ids are unique, but node values may repeat
• p_id and q_id are distinct and both exist in the tree

Examples

Solution

def solution(tree, p_id, q_id):
    if tree is None:
        return None

    root_id = tree[0]
    res = {}
    lca_id = None

    stack = [(tree, False)]  # (node, visited)
    while stack:
        node, visited = stack.pop()
        if node is None:
            continue
        node_id, _, children = node
        if not visited:
            stack.append((node, True))
            for child in children:
                stack.append((child, False))
        else:
            found_p = (node_id == p_id)
            found_q = (node_id == q_id)
            for child in children:
                cid = child[0]
                cp, cq = res.get(cid, (False, False))
                if cp:
                    found_p = True
                if cq:
                    found_q = True
            if lca_id is None and found_p and found_q:
                lca_id = node_id
            res[node_id] = (found_p, found_q)

    rp, rq = res.get(root_id, (False, False))
    return lca_id if rp and rq else None

Time complexity: O(n). Space complexity: O(h), where h is the height of the tree due to recursion stack.

Hints

1. Let each DFS call return two booleans: whether p was found in the current subtree and whether q was found in the current subtree.
2. Use postorder traversal. If children are processed before the current node, the first node whose returned pair becomes (True, True) is the deepest common ancestor.