{x}
blog image

Step-By-Step Directions From a Binary Tree Node to Another

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

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

  • 'L' means to go from a node to its left child node.
  • 'R' means to go from a node to its right child node.
  • 'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

 

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

 

Constraints:

  • The number of nodes in the tree is n.
  • 2 <= n <= 105
  • 1 <= Node.val <= n
  • All the values in the tree are unique.
  • 1 <= startValue, destValue <= n
  • startValue != destValue

Solution Explanation: Step-by-Step Directions From a Binary Tree Node to Another

This problem asks for the shortest path between two nodes in a binary tree, represented as a string of 'L', 'R', and 'U' characters. Two solutions are presented, both leveraging the concept of the Lowest Common Ancestor (LCA).

Core Idea: The shortest path between two nodes always goes through their Lowest Common Ancestor (LCA). The LCA is the lowest node in the tree that is an ancestor of both nodes.

Solution 1: LCA + Separate DFS

This approach involves three steps:

  1. Find the LCA: A recursive function lca finds the LCA of startValue and destValue. It returns the LCA node. If a node's value matches either startValue or destValue, it's the LCA if it's an ancestor of both; otherwise it continues recursively through left and right subtrees.

  2. DFS from LCA to targets: Two separate Depth-First Searches (dfs) are used, one starting from the LCA node and going to startValue, and the other going to destValue. Each dfs generates a path string ('L' or 'R' for each step).

  3. Construct the final path: The path from the LCA to startValue is reversed and represented by 'U' characters (because we're going up the tree). This reversed path and the path from the LCA to destValue are concatenated to form the final result.

Solution 2: LCA + Single DFS (Optimized)

This solution is more efficient by avoiding the separate DFS calls. Instead:

  1. DFS from root to targets: A single dfs function is used twice, once for each node (startValue and destValue). Each call builds the path from the root to the target node.

  2. Find common prefix and construct path: It finds the longest common prefix between the two path strings. The portion of the startValue path beyond the common prefix is converted to 'U' characters, and this is concatenated with the remaining portion of the destValue path. This directly gives the shortest path.

Time and Space Complexity:

Both solutions have the same complexity:

  • Time Complexity: O(N) - Both solutions traverse the tree at most twice (once for each DFS, or essentially twice for Solution 2). N represents the number of nodes in the tree.

  • Space Complexity: O(N) - In the worst-case scenario (a skewed tree), the recursive depth of the DFS can be O(N), thus leading to O(N) space usage for the call stack and the path strings.

Code Examples (Python):

Solution 1:

def getDirections(root, startValue, destValue):
    def lca(node, p, q):
        if not node or node.val in (p, q):
            return node
        left = lca(node.left, p, q)
        right = lca(node.right, p, q)
        return node if left and right else left or right
 
    def dfs(node, target, path):
        if not node:
            return False
        if node.val == target:
            return True
        path.append("L")
        if dfs(node.left, target, path):
            return True
        path[-1] = "R"
        if dfs(node.right, target, path):
            return True
        path.pop()
        return False
 
    l = lca(root, startValue, destValue)
    path1, path2 = [], []
    dfs(l, startValue, path1)
    dfs(l, destValue, path2)
    return "U" * len(path1) + "".join(path2)

Solution 2:

def getDirections(root, startValue, destValue):
    def dfs(node, target, path):
        if not node:
            return False
        if node.val == target:
            return True
        path.append("L")
        if dfs(node.left, target, path):
            return True
        path[-1] = "R"
        if dfs(node.right, target, path):
            return True
        path.pop()
        return False
 
    path1, path2 = [], []
    dfs(root, startValue, path1)
    dfs(root, destValue, path2)
    i = 0
    while i < len(path1) and i < len(path2) and path1[i] == path2[i]:
        i += 1
    return "U" * (len(path1) - i) + "".join(path2[i:])

The code in other languages (Java, C++, Go, TypeScript, JavaScript) follows similar logic, with appropriate adjustments for syntax and data structures. Solution 2 is generally preferred due to its slightly cleaner implementation and avoidance of redundant LCA finding.