Lowest Common Ancestor in an Explicit Binary Tree

The report identifies the LCA problem by name without a variant or representation. This executable practice version explicitly chooses an arbitrary binary tree with existing target nodes and the array representation below.

Implement lowest_common_ancestor(left, right, root, p, q) -> int:

• left: int[] and right: int[] have the same length n.
• Node IDs are the integers from 0 through n - 1. left[i] and right[i] identify node i's children; -1 means no child.
• root: int is the root node ID, and p: int, q: int are target node IDs.
• Return the node ID of their lowest common ancestor.

Constraints & Assumptions

• 1 <= n <= 100000.
• The arrays describe a valid rooted binary tree: all nodes are reachable from root, there are no cycles, and every non-root node has exactly one parent.
• Both targets exist and may be identical. IDs identify nodes; their numeric order has no relationship to tree position.
• The tree is not required to satisfy any binary-search-tree ordering.
• A target can be an ancestor of the other target. The tree may be a chain, so do not assume shallow recursion.

Examples

left = [1, -1, -1]
right = [2, -1, -1]
root = 0, p = 1, q = 2
result = 0

left = [1, 3, -1, -1, -1]
right = [2, 4, -1, -1, -1]
root = 0, p = 3, q = 4
result = 1