Compute shortest path between two tree nodes
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a binary tree (not necessarily a BST) and two node values u and v, implement a function that returns the shortest path between them as a list of node values. Optimize for multiple queries by describing preprocessing strategies (e.g., storing parent pointers, Euler tour + RMQ LCA, or binary lifting). Discuss time/space trade-offs and how to handle missing nodes, duplicate values, and very deep trees.
Quick Answer: This question evaluates understanding of tree algorithms and preprocessing techniques for efficient path queries, along with robustness in handling missing or duplicate node values and very deep trees.