Constraints

• 0 <= len(nodes) <= 100000
• If nodes is non-empty, node 0 is the root.
• Each child index is either -1 or a valid node index.
• The input structure is a valid binary tree.
• All node values are unique.
• The returned path length is not counted as extra space.

Examples

Solution

def solution(nodes, u, v):
    if not nodes:
        return []

    path_u = None
    path_v = None
    current = []
    stack = [(0, 0)]

    while stack:
        index, state = stack.pop()
        if index == -1 or index < 0 or index >= len(nodes):
            continue

        if state == 0:
            value, left, right = nodes[index]
            current.append(value)

            if value == u:
                path_u = current[:]
            if value == v:
                path_v = current[:]

            if path_u is not None and path_v is not None:
                break

            stack.append((index, 1))
            if right != -1:
                stack.append((right, 0))
            if left != -1:
                stack.append((left, 0))
        else:
            current.pop()

    if path_u is None or path_v is None:
        return []

    common = 0
    limit = min(len(path_u), len(path_v))
    while common < limit and path_u[common] == path_v[common]:
        common += 1

    lca_pos = common - 1
    return path_u[lca_pos:][::-1] + path_v[common:]

Time complexity: O(n), where n is the number of nodes.. Space complexity: O(h) extra space excluding the returned path, where h is the tree height..

Hints

1. Find the path from the root to u and the path from the root to v. Their longest common prefix ends at the LCA.
2. Once you know the LCA position, reverse the suffix of the u path up to the LCA, then append the suffix of the v path below the LCA.

Constraints

• 0 <= len(nodes) <= 2000
• If nodes is non-empty, node 0 is the root.
• Each child index is either -1 or a valid node index.
• The input structure is a valid binary tree.
• All node values are unique.

Examples

Solution

def solution(nodes, u, v):
    def combine_value_paths(path_a, path_b):
        if path_a is None or path_b is None:
            return []
        common = 0
        limit = min(len(path_a), len(path_b))
        while common < limit and path_a[common] == path_b[common]:
            common += 1
        lca_pos = common - 1
        return path_a[lca_pos:][::-1] + path_b[common:]

    def recursive_path(target):
        path = []

        def dfs(index):
            if index == -1 or index < 0 or index >= len(nodes):
                return False
            value, left, right = nodes[index]
            path.append(value)
            if value == target:
                return True
            if dfs(left) or dfs(right):
                return True
            path.pop()
            return False

        if not nodes or not dfs(0):
            return None
        return path

    def recursive_result():
        return combine_value_paths(recursive_path(u), recursive_path(v))

    def iterative_result():
        if not nodes:
            return []

        parent = {0: -1}
        value_to_index = {}
        visited = set()
        stack = [0]

        while stack:
            index = stack.pop()
            if index in visited or index < 0 or index >= len(nodes):
                continue
            visited.add(index)
            value, left, right = nodes[index]
            value_to_index[value] = index

            if right != -1 and 0 <= right < len(nodes):
                parent[right] = index
                stack.append(right)
            if left != -1 and 0 <= left < len(nodes):
                parent[left] = index
                stack.append(left)

        if u not in value_to_index or v not in value_to_index:
            return []

        def root_path(index):
            result = []
            while index != -1:
                result.append(index)
                index = parent[index]
            return result[::-1]

        path_u = root_path(value_to_index[u])
        path_v = root_path(value_to_index[v])

        common = 0
        limit = min(len(path_u), len(path_v))
        while common < limit and path_u[common] == path_v[common]:
            common += 1

        lca_pos = common - 1
        index_path = path_u[lca_pos:][::-1] + path_v[common:]
        return [nodes[index][0] for index in index_path]

    return [recursive_result(), iterative_result()]

Time complexity: Recursive implementation: O(n). Iterative implementation: O(n). The combined function is O(n) with a constant-factor overhead.. Space complexity: Recursive implementation: O(h) call stack plus path storage. Iterative implementation: O(n) for parent pointers, visited set, and stack..

Hints

1. The recursive version can search for a root-to-target path by appending on entry and popping on backtracking.
2. The iterative version can build parent pointers with an explicit stack, then walk from each target up to the root.

Constraints

• 0 <= len(nodes) <= 100000
• 0 <= len(queries) <= 100000
• If nodes is non-empty, node 0 is the root.
• Each child index is either -1 or a valid node index.
• The input structure is a valid binary tree.
• All node values are unique.

Examples

Solution

def solution(nodes, queries):
    if not queries:
        return []

    n = len(nodes)
    if n == 0:
        return [[] for _ in queries]

    log = 1
    while (1 << log) <= n:
        log += 1

    parent = [-1] * n
    depth = [0] * n
    visited = [False] * n
    value_to_index = {}

    stack = [0]
    while stack:
        index = stack.pop()
        if index < 0 or index >= n or visited[index]:
            continue
        visited[index] = True
        value, left, right = nodes[index]
        value_to_index[value] = index

        if right != -1 and 0 <= right < n:
            parent[right] = index
            depth[right] = depth[index] + 1
            stack.append(right)
        if left != -1 and 0 <= left < n:
            parent[left] = index
            depth[left] = depth[index] + 1
            stack.append(left)

    up = [[-1] * n for _ in range(log)]
    up[0] = parent[:]
    for k in range(1, log):
        for index in range(n):
            mid = up[k - 1][index]
            up[k][index] = -1 if mid == -1 else up[k - 1][mid]

    def lift(index, distance):
        bit = 0
        while distance > 0 and index != -1:
            if distance & 1:
                index = up[bit][index]
            distance >>= 1
            bit += 1
        return index

    def lca(a, b):
        if depth[a] < depth[b]:
            a, b = b, a
        a = lift(a, depth[a] - depth[b])
        if a == b:
            return a
        for k in range(log - 1, -1, -1):
            if up[k][a] != up[k][b]:
                a = up[k][a]
                b = up[k][b]
        return parent[a]

    def build_path(a, b):
        c = lca(a, b)
        if c == -1:
            return []

        left_part = []
        x = a
        while x != c:
            left_part.append(nodes[x][0])
            x = parent[x]
        left_part.append(nodes[c][0])

        right_part = []
        x = b
        while x != c:
            right_part.append(nodes[x][0])
            x = parent[x]

        return left_part + right_part[::-1]

    answers = []
    for query in queries:
        u, v = query[0], query[1]
        if u not in value_to_index or v not in value_to_index:
            answers.append([])
        else:
            answers.append(build_path(value_to_index[u], value_to_index[v]))

    return answers

Time complexity: Preprocessing is O(n log n). Each query is O(log n + L), where L is the length of the returned path.. Space complexity: O(n log n) for the binary-lifting table, plus O(n) for parent, depth, and value-index maps..

Hints

1. Precompute each node parent and depth. Then binary lifting can find LCAs in O(log n) time.
2. Even with fast LCA, outputting the path still costs time proportional to the number of nodes in that path.

Constraints

• 0 <= len(nodes) <= 100000
• Node values may be duplicated.
• If nodes is non-empty, node 0 is the root.
• Each child index is either -1 or a valid node index.
• Only nodes reachable from root index 0 are considered present in the tree.
• The implementation should avoid recursion.

Examples

Solution

def solution(nodes, u, v):
    n = len(nodes)
    if n == 0 or u < 0 or v < 0 or u >= n or v >= n:
        return []

    parent = {0: -1}
    visited = set()
    stack = [0]

    while stack:
        index = stack.pop()
        if index in visited:
            continue
        visited.add(index)

        value, left, right = nodes[index]
        if right != -1 and 0 <= right < n and right not in parent:
            parent[right] = index
            stack.append(right)
        if left != -1 and 0 <= left < n and left not in parent:
            parent[left] = index
            stack.append(left)

    if u not in visited or v not in visited:
        return []

    if u == v:
        return [nodes[u][0]]

    ancestors = set()
    x = u
    while x != -1:
        ancestors.add(x)
        x = parent.get(x, -1)

    path_from_v_up = []
    x = v
    lca = -1
    while x != -1:
        if x in ancestors:
            lca = x
            break
        path_from_v_up.append(x)
        x = parent.get(x, -1)

    if lca == -1:
        return []

    path_indices = []
    x = u
    while x != lca:
        path_indices.append(x)
        x = parent[x]
    path_indices.append(lca)
    path_indices.extend(reversed(path_from_v_up))

    return [nodes[index][0] for index in path_indices]

Time complexity: O(n) per call, where n is the number of nodes, plus O(L) to produce the returned path of length L.. Space complexity: O(n) for parent pointers, visited nodes, and ancestor tracking..

Hints

1. Use an explicit stack to traverse from the root and build parent pointers for reachable nodes.
2. After parent pointers are available, find the first common ancestor by walking upward from one endpoint.