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

Medium

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

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the binary tree contain duplicate node values?
Are `startValue` and `destValue` guaranteed to exist in the tree?
If `startValue` and `destValue` are the same, should I return an empty string, or a path representing traversal back to the same node (e.g., "")?
Can the tree be empty or contain only one node?
Are node values unique within the tree, aside from potential duplicates as mentioned earlier?

Brute Force Solution

Approach

The brute force approach is all about trying every single path. We will explore every possible route from the starting node to the destination node within the binary tree, one by one, until we find the correct directions.

Here's how the algorithm would work step-by-step:

Start at the starting node and try going 'up' towards the root.
From each node you reach, also try going 'left' and 'right'.
Keep doing this, exploring all possible combinations of 'up', 'left', and 'right' movements.
As you explore each path, check if you've reached the destination node.
If you reach the destination, save the series of 'up', 'left', and 'right' moves you took to get there.
Continue exploring all other possible paths, even if you've found a solution already.
Once you've explored every possibility, choose the shortest path you found. That's your answer.

Code Implementation

def find_path_brute_force(root, start_value, destination_value):
    shortest_path = None

    def find_node(node, value):
        if not node:
            return None
        if node.val == value:
            return node
        left_result = find_node(node.left, value)
        if left_result:
            return left_result
        return find_node(node.right, value)

    start_node = find_node(root, start_value)
    destination_node = find_node(root, destination_value)

    def explore_paths(current_node, current_path):
        nonlocal shortest_path

        if not current_node:
            return

        if current_node == destination_node:
            # We found a path to the destination, check if it's the shortest
            if shortest_path is None or len(current_path) < len(shortest_path):
                shortest_path = current_path
            return

        # Explore going 'up' (to the parent)
        if current_node.parent:

            explore_paths(current_node.parent, current_path + ['U'])

        # Explore going 'left'
        if current_node.left:
            explore_paths(current_node.left, current_path + ['L'])

            # Explore going 'right'
        if current_node.right:
            explore_paths(current_node.right, current_path + ['R'])

    # Add a parent attribute to each node.
    def add_parent_pointers(node, parent):
        if not node:
            return
        node.parent = parent
        add_parent_pointers(node.left, node)
        add_parent_pointers(node.right, node)

    add_parent_pointers(root, None)

    # Initiate the search from the starting node with an empty path.
    explore_paths(start_node, [])

    return ''.join(shortest_path) if shortest_path else ""

Big(O) Analysis

Time Complexity

O(4^n) – The brute force approach explores all possible paths from the start node to the destination node by trying every combination of 'U', 'L', and 'R' moves at each node. In the worst-case scenario, we may have to explore almost every node in the tree from every other node. The number of possible paths grows exponentially with the depth of the tree, as for each node we explore three branches ('U', 'L', 'R'), leading to a branching factor of 3 (plus the initial path). If the tree has n nodes, the depth could be proportional to n and thus we're potentially examining 4^n possible paths. Therefore, the time complexity of this approach is O(4^n).

Space Complexity

O(N) – The brute force approach explores all possible paths using recursion. In the worst case, the recursion depth could reach N, where N is the number of nodes in the binary tree. Each recursive call creates a new stack frame, thus the maximum space used by the call stack would be proportional to the height of the tree, which can be N in a skewed tree, to store the sequence of 'up', 'left', and 'right' moves for each possible path. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The core idea is to find the meeting point, or lowest common ancestor, of the two nodes in the tree. Then, we build paths from each node to that meeting point and combine them appropriately to get the directions.

Here's how the algorithm would work step-by-step:

First, find the shared ancestor node closest to both the starting and destination nodes.
Determine the path (sequence of 'U' for up, 'L' for left, 'R' for right) from the starting node to this common ancestor.
Determine the path from the common ancestor to the destination node.
Replace the path from the starting node to the common ancestor with a series of 'U' (up) moves since we are going up towards the root.
Combine the 'U' path with the path from the common ancestor to the destination node to form the complete path.
The combined path represents the step-by-step directions.

Code Implementation

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

def step_by_step_directions(
        root: TreeNode, start_value: int, destination_value: int) -> str:

    def find_node(node: TreeNode, target_value: int) -> TreeNode:
        if not node:
            return None
        if node.val == target_value:
            return node
        left_node = find_node(node.left, target_value)
        if left_node:
            return left_node
        return find_node(node.right, target_value)

    start_node = find_node(root, start_value)
    destination_node = find_node(root, destination_value)

    def get_path_to_ancestor(node: TreeNode, target: TreeNode, path: str) -> str:
        if node is None:
            return None
        if node == target:
            return path

        # Explore the left subtree
        left_path = get_path_to_ancestor(node.left, target, path + 'L')
        if left_path:
            return left_path

        # Explore the right subtree
        right_path = get_path_to_ancestor(node.right, target, path + 'R')
        if right_path:
            return right_path

        return None

    # Finds the lowest common ancestor (LCA).
    def find_lowest_common_ancestor(
            node: TreeNode, start_node: TreeNode, destination_node: TreeNode) -> TreeNode:
        if not node:
            return None

        if node == start_node or node == destination_node:
            return node

        left_lca = find_lowest_common_ancestor(node.left, start_node, destination_node)
        right_lca = find_lowest_common_ancestor(node.right, start_node, destination_node)

        if left_lca and right_lca:
            return node

        return left_lca if left_lca else right_lca

    lowest_common_ancestor = find_lowest_common_ancestor(root, start_node, destination_node)

    # Find path from start node to LCA
    start_to_lca_path = get_path_to_ancestor(lowest_common_ancestor, start_node, '')

    # Find path from LCA to destination node.
    lca_to_destination_path = get_path_to_ancestor(lowest_common_ancestor, destination_node, '')

    # Replace path from start to LCA with 'U's.
    up_moves = 'U' * len(start_to_lca_path)

    return up_moves + lca_to_destination_path

Big(O) Analysis

Time Complexity

O(n) – Finding the lowest common ancestor (LCA) in a binary tree typically takes O(n) time, as it may involve traversing the entire tree in the worst case. Building the paths from the start node and the destination node to the LCA also takes O(n) time in the worst-case scenario, where n is the number of nodes in the tree. Replacing the start node path with 'U' characters and concatenating the paths are operations that take time proportional to the lengths of the paths, which are bounded by the height of the tree which is at most n. Therefore, the dominant operations are finding the LCA and constructing the paths, both of which take O(n) time, resulting in an overall time complexity of O(n).

Space Complexity

O(N) – The space complexity is dominated by the recursive calls used to find the paths from the starting and destination nodes to the lowest common ancestor. In the worst-case scenario, the tree could be a skewed tree, resembling a linked list, where the recursion depth could be proportional to the number of nodes, N. Thus, the recursion stack would consume O(N) space. Additionally, storing the paths from the nodes to the ancestor would take O(N) space in the worst case.

Edge Cases

Case	How to Handle
Root is null	Return an empty string or null, as no path can exist from a null root.
Start node and destination node are the same	Return an empty string indicating zero moves are needed.
Either startValue or destValue does not exist in the tree	Return an appropriate error (null, exception) indicating no path exists.
Large tree, potential for stack overflow with recursion	Consider an iterative approach or a limited recursion depth to avoid stack overflow errors.
Start node is an ancestor of the destination node	The path should only contain 'D' (down) moves from the start to the destination.
Destination node is an ancestor of the start node	The path should only contain 'U' (up) moves from the start to the destination.
The tree is a skewed tree (all nodes on one side)	The solution should correctly handle traversal even in the case of a skewed tree.
Integer overflow if node values are large	Node values are typically not directly used to compute path, this is not an issue.