<p>You are given the <code>root</code> of a <strong>binary tree</strong> with <code>n</code> nodes. Each node is uniquely assigned a value from <code>1</code> to <code>n</code>. You are also given an integer <code>startValue</code> representing the value of the start node <code>s</code>, and a different integer <code>destValue</code> representing the value of the destination node <code>t</code>.</p>

<p>Find the <strong>shortest path</strong> starting from node <code>s</code> and ending at node <code>t</code>. Generate step-by-step directions of such path as a string consisting of only the <strong>uppercase</strong> letters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;U&#39;</code>. Each letter indicates a specific direction:</p>

<ul>
	<li><code>&#39;L&#39;</code> means to go from a node to its <strong>left child</strong> node.</li>
	<li><code>&#39;R&#39;</code> means to go from a node to its <strong>right child</strong> node.</li>
	<li><code>&#39;U&#39;</code> means to go from a node to its <strong>parent</strong> node.</li>
</ul>

<p>Return <em>the step-by-step directions of the <strong>shortest path</strong> from node </em><code>s</code><em> to node</em> <code>t</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;" />
<pre>
<strong>Input:</strong> root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
<strong>Output:</strong> &quot;UURL&quot;
<strong>Explanation:</strong> The shortest path is: 3 &rarr; 1 &rarr; 5 &rarr; 2 &rarr; 6.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;" />
<pre>
<strong>Input:</strong> root = [2,1], startValue = 2, destValue = 1
<strong>Output:</strong> &quot;L&quot;
<strong>Explanation:</strong> The shortest path is: 2 &rarr; 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are <strong>unique</strong>.</li>
	<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>
	<li><code>startValue != destValue</code></li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        stack = [(root, 0)]
        src_node = None
        dest_node = None
        while stack:
            node, depth = stack.pop()
            node.depth = depth
            if node.val == startValue:
                src_node = node
            elif node.val == destValue:
                dest_node = node
            if src_node and dest_node:
                break
            if node.right:
                node.right.parent = node
                stack.append((node.right, depth + 1))
            if node.left:
                node.left.parent = node
                stack.append((node.left, depth + 1))
        up_path = []
        down_path = []

        while src_node.depth > dest_node.depth:
            src_node = src_node.parent
            up_path.append('U')
        while dest_node.depth > src_node.depth:
            if dest_node.parent.left == dest_node:
                down_path.append('L')
            else:
                down_path.append('R')
            dest_node = dest_node.parent
        while src_node != dest_node:
            up_path.append('U')
            if dest_node.parent.left == dest_node:
                down_path.append('L')
            else:
                down_path.append('R')
            src_node = src_node.parent
            dest_node = dest_node.parent
        return ''.join(up_path + down_path[::-1])

































"""
# Took too long but I think I have the right approach:
# 1. bfs from root storing the nodes as we go
# 2. once path from root to a and root to b are found, break
# 3. find lca of patha and pathb
# 4. 'U' * len(patha_to_lca) - 1 as starting result
# 5. find l/r directions from lca to b
# """
# from collections import deque
# # Definition for a binary tree node.
# # class TreeNode:
# #     def __init__(self, val=0, left=None, right=None):
# #         self.val = val
# #         self.left = left
# #         self.right = right

# class Solution:
#     def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
#         queue = deque()
#         queue.append((root, [], []))
#         node_a_path = []
#         node_b_path = []
#         node_b_dirs = []
#         while queue:
#             node, path, dirs = queue.popleft()
#             if node.val == startValue:
#                 node_a_path = path + [node]
#             elif node.val == destValue:
#                 node_b_path = path + [node]
#                 node_b_dirs = dirs
#             if node_a_path and node_b_path:
#                 break
#             if node.left:
#                 queue.append((node.left, path + [node], dirs + ['L']))
#             if node.right:
#                 queue.append((node.right, path + [node], dirs + ['R']))
#         lca_idx = 0
#         print([n.val for n in node_a_path])
#         print([n.val for n in node_b_path])
#         for i in range(0, len(node_a_path)):
#             if i >= len(node_b_path):
#                 lca_idx = i - 1
#                 break
#             elif node_a_path[i] != node_b_path[i]:
#                 lca_idx = i
#                 break
#         result = []
#         if len(node_a_path) > 1:
#             result += ['U'] * (len(node_a_path) - lca_idx)
#         result += node_b_dirs[lca_idx-1:]
#         return ''.join(result)























# # class Solution:
# #     def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
# #         # add up edges
# #         # run bfs from node a looking for b
# #         # store the seq of moves since node a
# #         # when b is found, return that seq
# #         nodea_from_root = None
# #         nodeb_from_root = None
# #         queue = deque()
# #         queue.append((root, []))
# #         while queue:
# #             node, path = queue.popleft()
# #             if node.val == startValue:
# #                 nodea_from_root = path + [node]
# #             if node.val == destValue:
# #                 nodeb_from_root = path + [node]
# #             if nodea_from_root and nodeb_from_root:
# #                 break
# #             if node.left:
# #                 queue.append((node.left, path + [node]))
# #             if node.right:
# #                 queue.append((node.right, path + [node]))
# #         print([node.val for node in nodea_from_root] + [node.val for node in nodeb_from_root])
# #         nodes_in_b = {n for n in nodeb_from_root}
# #         lca = None
# #         for i in range(len(nodea_from_root) - 1, -1, -1):
# #             if nodea_from_root[i] in nodes_in_b:
# #                 lca = nodea_from_root[i]
# #                 nodea_from_root = nodea_from_root[i:]
# #                 break
# #         for i in range(0, len(nodeb_from_root)):
# #             if nodeb_from_root[i] == lca:
# #                 nodeb_from_root = nodeb_from_root[i:]
# #         print([node.val for node in nodea_from_root] + [node.val for node in nodeb_from_root])
# #         result = ['U'] * (len(nodea_from_root) - 1)
# #         for i in range(len(nodeb_from_root) - 1):
# #             if nodeb_from_root[i].left == nodeb_from_root[i+1]:
# #                 result += ['L']
# #             elif nodeb_from_root[i].right == nodeb_from_root[i+1]:
# #                 result += ['R']
# #         return ''.join(result)
# #         # return ''.join(['U'] * len(nodea_from_root) + nodeb_from_root)
                
61181