Katkat
Back

Compute shortest path between tree nodes

SnowflakeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.