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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

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, and '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.

Key Insights

  • The problem requires finding a path in a binary tree from one node to another.
  • The path consists of moving down to children (left or right) and moving up to the parent (up).
  • We need to find the lowest common ancestor (LCA) of the two nodes to efficiently navigate from the start node to the destination node.
  • The solution involves a traversal of the tree to locate both nodes and build the path based on their relationship to the LCA.

Space and Time Complexity

Time Complexity: O(n) - We may need to visit all nodes in the worst case to find both nodes and their LCA. Space Complexity: O(h) - The space complexity is determined by the height of the tree due to recursive stack space.

Solution

To solve the problem, we can use Depth-First Search (DFS) to find both the start and destination nodes while also determining their lowest common ancestor (LCA). We will keep track of the path from the start node to the LCA and then the path from the LCA to the destination node. The final output will concatenate these paths, using 'U' for upward movements to the parent and 'L' or 'R' for downward movements to the children.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def getDirections(root, startValue, destValue):
    # To store the paths from start and destination to the LCA
    path_to_start = []
    path_to_dest = []

    # Find both nodes and their LCA
    lca = findLCA(root, startValue, destValue, path_to_start, path_to_dest)

    # Create the final path from start to dest
    directions = 'U' * len(path_to_start)  # Move up to LCA
    directions += ''.join(path_to_dest)    # Move down to destination
    return directions

def findLCA(node, startValue, destValue, path_to_start, path_to_dest):
    if not node:
        return None
    if node.val == startValue:
        path_to_start.append(node.val)
        return node
    if node.val == destValue:
        path_to_dest.append(node.val)
        return node
    
    # Traverse left and right
    left_lca = findLCA(node.left, startValue, destValue, path_to_start, path_to_dest)
    right_lca = findLCA(node.right, startValue, destValue, path_to_start, path_to_dest)

    if left_lca and right_lca:
        return node  # This is the LCA

    if left_lca:
        path_to_start.append('L')
        return left_lca
    if right_lca:
        path_to_start.append('R')
        return right_lca

    return None
← Back to All Questions