#2096

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

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

Find the shortest path between two nodes in a binary tree and output the directions as a string of 'L', 'R', and 'U'.

string tree depth first search binary tree

Problem Statement

You are given a binary tree with unique node values ranging from 1 to n. The root node is provided, along with a start node value and a destination node value. The task is to find the shortest path between these two nodes and return the directions in a string of 'L', 'R', and 'U'. 'L' means left, 'R' means right, and 'U' means up. Each direction corresponds to a step taken from one node to the next.

The shortest path between the start and destination nodes in the tree will pass through their Lowest Common Ancestor (LCA). You are to first trace a path upwards from the start node to the LCA, and then trace a path downwards to the destination node. The directions should reflect these movements with 'U' for upward, 'L' for left, and 'R' for right steps.

Examples

Example 1

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6

Output: "UURL"

The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2

Input: root = [2,1], startValue = 2, destValue = 1

Output: "L"

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 Approach

Finding the Lowest Common Ancestor (LCA)

The shortest path between two nodes in a binary tree always passes through their Lowest Common Ancestor. By first identifying the LCA of the start and destination nodes, we can separate the path into two parts: one moving upwards from the start node, and the other moving downwards to the destination node.

Traversal Strategy

Once the LCA is found, the algorithm performs a DFS or BFS traversal to move up from the start node to the LCA, recording 'U' for each step. Then, it traces the path from the LCA to the destination node, recording 'L' or 'R' depending on whether the next step is to the left or right child.

Efficient Path Reconstruction

The path can be constructed efficiently by keeping track of the traversal from the start node to the LCA and from the LCA to the destination node. With a time complexity of O(n), we ensure that the traversal is completed in linear time, suitable for the input size of up to 10^5 nodes.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity of this solution is O(n) because we need to visit each node once to find the LCA and reconstruct the path. The space complexity is also O(n) due to the recursion stack or BFS queue used during the traversal.

What Interviewers Usually Probe

Look for an understanding of tree traversal techniques, especially in the context of Lowest Common Ancestor (LCA).
Check for an efficient approach, where the traversal doesn't revisit nodes unnecessarily.
Expect clarity in constructing the path with the correct sequence of 'L', 'R', and 'U' directions.

Common Pitfalls or Variants

Common pitfalls

Confusing the order of traversal—ensure the solution moves up first and then down to the destination node.
Overcomplicating the LCA search—opt for a simple recursive or iterative approach.
Failing to handle edge cases, such as when the start node is the parent of the destination node.

Follow-up variants

The problem can be varied by providing additional constraints, such as limiting the tree to binary search trees (BST).
Another variant might require returning the path as an array of node values instead of directions.
For larger trees, the pathfinding method could be tested with variations in node depth or balance.

FAQ

What is the Lowest Common Ancestor (LCA) in this problem?

The LCA is the deepest node that is an ancestor of both the start and destination nodes. The shortest path between them must pass through this node.

Why is the time complexity O(n) for this problem?

The algorithm traverses the tree once to find the LCA and then again to construct the path, resulting in linear time complexity relative to the number of nodes.

How can I avoid common mistakes in this problem?

Make sure you handle edge cases like when the start node is an ancestor of the destination node. Always prioritize identifying the LCA before constructing the path.

What patterns should I focus on to solve this problem?

Focus on tree traversal techniques, particularly DFS and BFS, and how to efficiently find the LCA in a binary tree.

How does this problem relate to other binary tree traversal problems?

This problem is a specific case of binary tree traversal, where you need to find a path between two nodes, utilizing the LCA and tree traversal methods like DFS or BFS.

terminal

Solution

Solution 1: Lowest Common Ancestor + DFS

We can first find the lowest common ancestor of nodes $\textit{startValue}$ and $\textit{destValue}$, denoted as $\textit{node}$. Then, starting from $\textit{node}$, we find the paths to $\textit{startValue}$ and $\textit{destValue}$ respectively. The path from $\textit{startValue}$ to $\textit{node}$ will consist of a number of $\textit{U}$s, and the path from $\textit{node}$ to $\textit{destValue}$ will be the $\textit{path}$. Finally, we concatenate these two paths.

# 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:
        def lca(node: Optional[TreeNode], p: int, q: int):
            if node is None or node.val in (p, q):
                return node
            left = lca(node.left, p, q)
            right = lca(node.right, p, q)
            if left and right:
                return node
            return left or right

        def dfs(node: Optional[TreeNode], x: int, path: List[str]):
            if node is None:
                return False
            if node.val == x:
                return True
            path.append("L")
            if dfs(node.left, x, path):
                return True
            path[-1] = "R"
            if dfs(node.right, x, path):
                return True
            path.pop()
            return False

        node = lca(root, startValue, destValue)

        path_to_start = []
        path_to_dest = []

        dfs(node, startValue, path_to_start)
        dfs(node, destValue, path_to_dest)

        return "U" * len(path_to_start) + "".join(path_to_dest)

Solution 2: Lowest Common Ancestor + DFS (Optimized)

We can start from $\textit{root}$, find the paths to $\textit{startValue}$ and $\textit{destValue}$, denoted as $\textit{pathToStart}$ and $\textit{pathToDest}$, respectively. Then, remove the longest common prefix of $\textit{pathToStart}$ and $\textit{pathToDest}$. At this point, the length of $\textit{pathToStart}$ is the number of $\textit{U}$s in the answer, and the path of $\textit{pathToDest}$ is the path in the answer. We just need to concatenate these two paths.

# 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:
        def lca(node: Optional[TreeNode], p: int, q: int):
            if node is None or node.val in (p, q):
                return node
            left = lca(node.left, p, q)
            right = lca(node.right, p, q)
            if left and right:
                return node
            return left or right

        def dfs(node: Optional[TreeNode], x: int, path: List[str]):
            if node is None:
                return False
            if node.val == x:
                return True
            path.append("L")
            if dfs(node.left, x, path):
                return True
            path[-1] = "R"
            if dfs(node.right, x, path):
                return True
            path.pop()
            return False

        node = lca(root, startValue, destValue)

        path_to_start = []
        path_to_dest = []

        dfs(node, startValue, path_to_start)
        dfs(node, destValue, path_to_dest)

        return "U" * len(path_to_start) + "".join(path_to_dest)

Continue Practicing

#2049 count nodes with the highest score #1028 recover a tree from preorder traversal #988 smallest string starting from leaf