Directions Along a Binary Tree Path

### Problem A binary tree contains `n` nodes with distinct values from `1` through `n`. Given the root and two different values `startValue` and `destValue`, return directions for the shortest route from the start node to the destination. Use `L` to move to a left child, `R` to move to a right child and `U` to move to a parent. Both values occur in the tree. ```cpp class Solution { public: string getDirections(TreeNode* root, int startValue, int destValue); }; ``` ### Examples **Example 1:** ```text Tree: root 1, left child 2, right child 3; node 2 has left child 4. startValue = 4, destValue = 3 Output: "UUR" Explanation: Move 4->2->1->3. ``` **Example 2:** ```text Tree: root 1 with right child 2. startValue = 1, destValue = 2 Output: "R" Explanation: The destination is the immediate right child. ``` ### Constraints - `2 <= n <= 10^5`. - Node values are unique and lie in `[1,n]`. - Both requested values exist and differ. ### Clarifying Questions TreeNode provides child pointers but no parent pointer. Return directions between the two requested nodes without changing the tree. ```hint Inspect the structure How does the shared prefix of root-to-node paths identify the point where directions turn upward to downward? ``` ### Reasoning checkpoints - Return a valid shortest direction string with every step interpreted from its current node. - Handle a start or destination that is an ancestor of the other, as well as nodes in different branches. - Preserve the tree and support the maximum possible depth and number of nodes. ### Optional extensions What preprocessing would help answer many direction queries on the same tree?