Quick Overview

Given a binary tree and two node values u and v, return the shortest path between them as an ordered list of node values. This Snowflake onsite question tests lowest-common-ancestor logic, path reconstruction, iterative vs. recursive implementation, complexity analysis, and preprocessing strategies (parent pointers, binary lifting, Euler tour + RMQ) for answering many queries efficiently.

Compute shortest path between tree nodes

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### 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.

Quick Answer: Given a binary tree and two node values u and v, return the shortest path between them as an ordered list of node values. This Snowflake onsite question tests lowest-common-ancestor logic, path reconstruction, iterative vs. recursive implementation, complexity analysis, and preprocessing strategies (parent pointers, binary lifting, Euler tour + RMQ) for answering many queries efficiently.

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

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)

Expected Output: [5, 2, 4]

Explanation: Node 5 is an ancestor of node 4, so the path goes downward through 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)

Expected 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

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)

Expected Output: [[6, 5, 2, 4], [6, 5, 2, 4]]

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

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)

Expected 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

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]])

Expected 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.

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

Expected 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

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

Expected Output: [3, 2, 1, 2, 3]

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

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

Expected 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.

Loading coding console...