Compute shortest path between tree nodes

Question

You are given the root of a binary tree (not necessarily a BST) whose nodes have integer values, and two target values u and v. Implement a function that returns the shortest path between u and v as a list of node values, in order from u to v. If either node does not exist in the tree, return an empty list.

Work through the following:

1. Core solution. Return the node-value sequence along the shortest path between u and v. Achieve O(n) time and O(h) extra space (where n is the number of nodes and h is the tree height) by finding the lowest common ancestor (LCA) of u and v and reconstructing the path from u up to the LCA and then down to v.
2. Implementations. Provide both an iterative and a recursive implementation, and analyze the time and space complexity of each.
3. Multiple queries. Suppose you must answer many (u, v) path queries on the same tree. Describe preprocessing strategies that speed up repeated queries — e.g. storing parent pointers, Euler tour + Range-Minimum-Query (RMQ) LCA, or binary lifting — and discuss the time/space trade-offs of each (preprocessing cost vs. per-query cost).
4. Robustness. Explain how your approach handles edge cases: missing nodes, the case u == v, one node being an ancestor of the other, duplicate values in the tree, and very deep (skewed) trees where recursion may overflow the call stack.

Part 1: Core LCA Path Between Two Values

You are given a binary tree that is not necessarily a BST. The tree is represented by an array of nodes, where nodes[i] = [value, left_index, right_index]. The root is node 0 when the tree is non-empty, and -1 means no child. All node values are unique. Given two target values u and v, return the shortest path between them as a list of node values from u to v. If either value is missing, return an empty list. The intended approach is to find the root-to-u and root-to-v paths, identify their lowest common ancestor, and combine the paths.

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

Example 1

Input: ([[3, 1, 2], [5, 3, 4], [1, 5, 6], [6, -1, -1], [2, 7, 8], [0, -1, -1], [8, -1, -1], [7, -1, -1], [4, -1, -1]], 5, 4)
Output: [5, 2, 4]

Explanation: Node 5 is an ancestor of node 4, so the path goes downward through 2.

Example 2

Input: ([[3, 1, 2], [5, 3, 4], [1, 5, 6], [6, -1, -1], [2, 7, 8], [0, -1, -1], [8, -1, -1], [7, -1, -1], [4, -1, -1]], 6, 8)
Output: [6, 5, 3, 1, 8]

Explanation: The LCA is the root value 3.

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.

Part 2: Compare Recursive and Iterative Tree Path Implementations

You are given a binary tree represented by nodes[i] = [value, left_index, right_index]. The tree is not necessarily a BST, and all values are unique. Given target values u and v, implement both a recursive and an iterative shortest-path computation. Return both results as [recursive_path, iterative_path]. If either target is missing, each implementation should return an empty path.

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

Example 1

Input: ([[3, 1, 2], [5, 3, 4], [1, 5, 6], [6, -1, -1], [2, 7, 8], [0, -1, -1], [8, -1, -1], [7, -1, -1], [4, -1, -1]], 6, 4)
Output: [[6, 5, 2, 4], [6, 5, 2, 4]]

Explanation: Both implementations should produce the same path through LCA value 5.

Example 2

Input: ([[3, 1, 2], [5, 3, 4], [1, 5, 6], [6, -1, -1], [2, 7, 8], [0, -1, -1], [8, -1, -1], [7, -1, -1], [4, -1, -1]], 3, 7)
Output: [[3, 5, 2, 7], [3, 5, 2, 7]]

Explanation: The root is one endpoint of the path.

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.

Part 3: Answer Many Tree Path Queries with Preprocessing

You are given one fixed binary tree and many path queries. The tree is represented by nodes[i] = [value, left_index, right_index], with unique values. For each query [u, v], return the shortest path from value u to value v as node values. If either value is missing, return [] for that query. Preprocess the tree once so repeated LCA queries are faster than scanning the whole tree each time.

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

Example 1

Input: ([[3, 1, 2], [5, 3, 4], [1, 5, 6], [6, -1, -1], [2, 7, 8], [0, -1, -1], [8, -1, -1], [7, -1, -1], [4, -1, -1]], [[6, 4], [5, 8], [7, 7], [5, 99]])
Output: [[6, 5, 2, 4], [5, 3, 1, 8], [7], []]

Explanation: Several queries reuse the same preprocessed tree. The missing value query returns an empty path.

Example 2

Input: ([], [[1, 2], [1, 1]])
Output: [[], []]

Explanation: All queries on an empty tree return empty paths.

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.

Part 4: Robust Path Queries with Duplicate Values and Deep Trees

In real trees, values may be duplicated, and recursion can overflow on very deep skewed trees. To make duplicate values unambiguous, this problem identifies endpoints by node index rather than by value. Given a binary tree represented by nodes[i] = [value, left_index, right_index] and two node indices u and v, return the shortest path from node u to node v as node values. If either index is invalid or not reachable from the root, return []. Your implementation should be iterative.

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

Example 1

Input: ([[1, 1, 2], [2, 3, -1], [2, -1, 4], [3, -1, -1], [3, -1, -1]], 3, 4)
Output: [3, 2, 1, 2, 3]

Explanation: Values 2 and 3 are duplicated, but node indices make the endpoints unambiguous.

Example 2

Input: ([[1, 1, 2], [2, 3, -1], [2, -1, 4], [3, -1, -1], [3, -1, -1]], 2, 2)
Output: [2]

Explanation: When both endpoint indices are the same, return that single node value.

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.

Solution

The unique tree path between u and v runs from u up to their lowest common ancestor, then down to v. Capture each node's root-to-node path during a single DFS (or record parent pointers during BFS for an iterative version), find the LCA as the last shared prefix element, then concatenate u->LCA reversed with LCA->v. Single query is O(n) time, O(h) space; for repeated queries, preprocess the LCA with parent pointers, binary lifting, or Euler tour + RMQ to trade O(n log n) setup for O(log n)/O(1) per-query lookups. Handle missing nodes, u==v, ancestor cases, duplicate values, and stack overflow on deep trees explicitly.

Approach

The shortest path between any two nodes in a tree is unique: it goes from u up to the lowest common ancestor (LCA) of u and v, then down to v. So the problem reduces to (a) locating both nodes, (b) finding their LCA, and (c) stitching the two root-to-node paths together at the LCA.

1. Core solution — O(n) time, O(h) space

The cleanest single-pass technique is to capture each node's root-to-node path while searching, then merge.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def path_between(root, u, v):
    # Find the root-to-target path as a list of node values.
    def find_path(node, target, acc):
        if not node:
            return False
        acc.append(node.val)
        if node.val == target:
            return True
        if find_path(node.left, target, acc) or find_path(node.right, target, acc):
            return True
        acc.pop()          # backtrack
        return False

    path_u, path_v = [], []
    if not find_path(root, u, path_u) or not find_path(root, v, path_v):
        return []          # either node missing

    # Find the LCA = last shared prefix element of the two root paths.
    i = 0
    while i < len(path_u) and i < len(path_v) and path_u[i] == path_v[i]:
        i += 1
    # path_u[i-1] is the LCA. Walk u -> LCA (reverse), then LCA -> v.
    # u up to and including LCA, reversed:
    up = path_u[i - 1:][::-1]
    # LCA exclusive down to v:
    down = path_v[i:]
    return up + down

find_path visits each node at most once, so the whole thing is O(n) time. The recursion stack and the two path lists are each at most the height of the tree, giving O(h) extra space.

2. Recursive vs. iterative

The code above is recursive. An iterative variant avoids deep call stacks by walking the tree with an explicit stack while recording each node's parent, then reconstructing paths from parent pointers:

def path_between_iter(root, u, v):
    if not root:
        return []
    parent = {root.val: None}
    seen = set()
    stack = [root]
    while stack and not ({u, v} <= seen):
        node = stack.pop()
        seen.add(node.val)
        for child in (node.left, node.right):
            if child:
                parent[child.val] = node.val
                stack.append(child)
    if u not in seen or v not in seen:
        return []

    # Collect ancestors of u (a set) walking up to the root.
    anc_u, cur = set(), u
    while cur is not None:
        anc_u.add(cur)
        cur = parent[cur]
    # Walk v up until we hit the first common ancestor (the LCA).
    down = []
    cur = v
    while cur not in anc_u:
        down.append(cur)
        cur = parent[cur]
    lca = cur
    # Walk u up to the LCA.
    up = []
    cur = u
    while cur != lca:
        up.append(cur)
        cur = parent[cur]
    up.append(lca)
    return up + down[::-1]

Both approaches are O(n) time. The recursive version is O(h) space; the iterative version is O(n) space because it records a parent for every visited node, but it cannot blow the call stack on a skewed tree.

3. Preprocessing for many queries

If you must answer many (u, v) queries on the same static tree, amortize the cost by preprocessing once. The path itself is still LCA + reconstruction; the optimization targets the LCA step.

Technique	Preprocessing	Per LCA query	Extra space	Notes
Parent pointers (walk up, mark ancestors)	O(n)	O(h)	O(n)	Simplest; degrades on deep/skewed trees
Binary lifting (up[k][node] = 2^k-th ancestor)	O(n log n)	O(log n)	O(n log n)	Great balance; easy to extend to k-th ancestor / distance
Euler tour + sparse-table RMQ	O(n log n) (or O(n) with ±1 RMQ)	O(1)	O(n log n)	Fastest queries; more code

Across many queries the choice is a preprocessing-vs-query trade-off: binary lifting or Euler+RMQ pay an O(n log n) upfront cost so each subsequent query is O(log n) or O(1), versus the O(h)-per-query of plain parent pointers. Note that finding the LCA gives you the meeting point; you still spend O(path length) to materialize the actual list of node values, so emitting the path is bounded below by its own length regardless of the LCA method.

4. Edge cases and robustness

• Missing node: if find_path/BFS never reaches u or v, return [].
• u == v: the path is just [u] (the loops above naturally produce a single-element list).
• Ancestor case (one node on the path to the other): the LCA is the ancestor itself; the up or down segment is empty and the merge still yields the correct straight-line path.
• Duplicate values: the problem is only well-defined for unique values, because a value no longer identifies a single node. If duplicates are possible, key on node identity/object references rather than on the integer value (the parent-pointer version generalizes by mapping nodes, not values), and clarify with the interviewer which occurrence is meant.
• Very deep / skewed trees: recursion depth equals tree height, so a near-linear chain can overflow the call stack. Prefer the iterative parent-pointer traversal (or raise the recursion limit / convert to an explicit stack) when the tree may be deep.

Final complexity for a single query: O(n) time, O(h) extra space (recursive) or O(n) (iterative). With preprocessing, queries drop to O(log n) (binary lifting) or O(1) (Euler+RMQ) for the LCA, plus O(path length) to emit the result.