We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 2217

Difficulty: Medium

Paid? No

Companies: TikTok, Google, Amazon, Databricks, Meta, Spotify, Snowflake

Problem Description

Given the root of a binary tree with unique node values, and two different target node values – startValue and destValue – find the shortest path from the start node to the destination node. The answer should be returned as a string consisting of characters ‘L’, ‘R’, and ‘U’ indicating moves to a node’s left child, right child, and parent respectively.

Key Insights

  • Find the path from the root to the start node and the root to the destination node using DFS.
  • Identify the last common node (i.e. the lowest common ancestor, LCA) by comparing the two paths.
  • The moves from the start node to the LCA are represented by ‘U’s.
  • The remaining part of the destination path (from the LCA to the destination node) provides the directions (‘L’ or ‘R’).
  • Concatenate the appropriate number of ‘U’s with the unique portion of the destination path to obtain the final direction string.

Space and Time Complexity

Time Complexity: O(n) – Traversing the tree using DFS and comparing paths takes linear time. Space Complexity: O(n) – In the worst-case scenario, the recursion stack and path storage will use linear space.

Solution

We solve the problem by:

  1. Using DFS to obtain the path from the root to the start node and from the root to the destination node. During DFS, we accumulate the direction taken (either ‘L’ or ‘R’).
  2. Comparing the two generated paths from the beginning to determine where they diverge. This divergence point corresponds to the lowest common ancestor (LCA).
  3. For the portion of the start path after the common part, each step is replaced by a ‘U’ (to move upward from the start node to the LCA).
  4. After reaching the LCA, append the remaining steps from the destination path to reach the destination node.
  5. Finally, return the concatenated instruction string.

The key data structures used are:

  • Vectors/arrays (or lists) to store the path for each target node.
  • Recursive DFS for tree traversal.

This approach ensures that we correctly translate the downward path information into the required “upward then downward” directions.

Code Solutions

# 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

# Function to perform DFS and find the path from the root to a target node.
# The path list will record 'L' or 'R' for each move from the current node.
def dfs(node, target, path):
    if node is None:
        return False
    if node.val == target:
        return True
    # Try left subtree
    path.append('L')
    if dfs(node.left, target, path):
        return True
    path.pop()
    # Try right subtree
    path.append('R')
    if dfs(node.right, target, path):
        return True
    path.pop()
    return False

def getDirections(root, startValue, destValue):
    # Get the paths from root to start and destination
    path_to_start = []
    path_to_dest = []
    
    dfs(root, startValue, path_to_start)
    dfs(root, destValue, path_to_dest)
    
    # Find the common prefix length (i.e. the LCA)
    i = 0
    while i < len(path_to_start) and i < len(path_to_dest) and path_to_start[i] == path_to_dest[i]:
        i += 1
    
    # Steps to move up from start to the LCA
    upward_moves = "U" * (len(path_to_start) - i)
    # Steps to move down from the LCA to the destination
    downward_moves = "".join(path_to_dest[i:])
    
    return upward_moves + downward_moves

# Example usage:
# Suppose we have a tree constructed and we need to call getDirections(root, startValue, destValue)
← Back to All Questions