Skip to main content
Talentd

Step-By-Step Directions From a Binary Tree Node to Another - Solution & Explanation

MediumStringTreeDepth-First SearchBinary Tree26 min readAsked at: Amazon, Meta, Snowflake +3
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a binary tree and two node values: startValue and destValue. The task is to return a string describing the directions to move from the start node to the destination node. Moves are encoded as L (left child), R (right child), and U (parent).

Approach 1: Find Paths to Root and Compute Directions (O(n) time, O(n) space)

This method finds the path from the root to both startValue and destValue using a DFS traversal. Each path records moves (L or R). Once both paths are found, iterate from the start of both arrays to locate the lowest common ancestor (LCA) where the paths diverge. For every remaining step in the start path, append U. Then append the remaining moves from the destination path. This approach works because the path from start to destination always goes up to the LCA and then down to the target. It relies heavily on recursive traversal of a binary tree using depth-first search.

Approach 2: Using Depth-First Search (DFS) to Build Parent Map (O(n) time, O(n) space)

Another strategy treats the tree like an undirected graph. Run a DFS to build a parent map for each node while also tracking whether the node is a left or right child. Once this structure is ready, perform a DFS or BFS starting from startValue. From any node you can move left, right, or up to the parent. Track visited nodes and accumulate direction characters (L, R, U) until destValue is reached. This approach is flexible because it converts the tree into a graph traversal problem and explores neighbors directly.

Recommended for interviews: The path comparison approach is typically expected. It clearly shows understanding of tree traversal and the concept of the lowest common ancestor. Building a parent map and exploring like a graph also works in O(n) time but uses a slightly heavier structure. Interviewers usually prefer the LCA-style path solution because the reasoning is simpler and the resulting code is shorter.

Approach 1: Find Paths to Root and Compute Directions

This approach involves finding the path from the start node to the root and the destination node to the root. Using these paths, the Lowest Common Ancestor (LCA) of the start and destination nodes is determined. This allows us to break down the path from start to destination as moving up towards the root to the LCA, then down towards the destination. Once these steps are identified, we can replace moves with correct directions ('L', 'R', 'U').

The code defines a TreeNode class with a method get_directions that computes the shortest path between two nodes in the form of directions. It uses a helper function path_to_node to traverse from the root to the specific node, appending 'L' or 'R' to a path list and returning True when the node is found. The main function finds paths to both start and destination nodes and calculates the direction by comparing the path steps. The paths are adjusted to determine when to move up and the remaining path to take.

Code

PythonC++Java

Python

C++

Java

Complexity

Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case.
Space Complexity: O(h), where h is the height of the tree due to recursion stack and storing paths.

Try this approach in the editor →

Approach 2: Using Depth-First Search (DFS) to Build Parent Map

This approach uses a DFS to build a parent map of nodes first. With this map, we can easily track the movement from any node to any other node. We then extract paths from startValue and destValue up to a common ancestor. The directions are computed through knowledge of parent-child relationships and mapped accordingly using 'L', 'R', and 'U'.

This solution creates a map of parent nodes using a depth-first search traversal. Once the parent map is available, the method accumulates paths from start and destination nodes to the root by tracking their parent relationships. Both paths are assessed for shared parent nodes to identify the LCA depth. The excess upward steps in the start path are marked with 'U', and further navigation from the LCA to the destination is indicated by the recorded 'L'/'R' movements.

Code

PythonJavaScriptC#

Python

JavaScript

C#

Complexity

Time Complexity: O(n), traversing all nodes for setup.
Space Complexity: O(n) due to the parent mapping.

Try this approach in the editor →

Approach 3: Lowest Common Ancestor + DFS

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

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Approach 4: Lowest Common Ancestor + DFS (Optimized)

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

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Find Paths to Root and Compute Directions

Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case.
Space Complexity: O(h), where h is the height of the tree due to recursion stack and storing paths.

Using Depth-First Search (DFS) to Build Parent Map

Time Complexity: O(n), traversing all nodes for setup.
Space Complexity: O(n) due to the parent mapping.

Lowest Common Ancestor + DFS—
Lowest Common Ancestor + DFS (Optimized)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Find Paths to Root and Compute DirectionsO(n)O(n)Best general solution. Clean logic using root-to-node paths and LCA comparison.
DFS Parent Map + Graph TraversalO(n)O(n)Useful when treating the tree as an undirected graph with parent links.

Video Solution

Step-By-Step Directions from a Binary Tree Node to Another - Leetcode 2096 - Python • NeetCodeIO • 15,401 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Step-By-Step Directions From a Binary Tree Node to Another easy or hard?
This problem is classified as Medium difficulty. The challenge comes from recognizing that the path between two nodes goes through their lowest common ancestor and translating that relationship into direction characters.
Step-By-Step Directions From a Binary Tree Node to Another Python/Java solution
Python and Java solutions typically implement DFS to build paths or parent maps. After identifying the lowest common ancestor or exploring neighbors, the algorithm constructs the direction string using 'L', 'R', and 'U'. Both implementations run in O(n) time and use O(n) auxiliary space.
How to solve Step-By-Step Directions From a Binary Tree Node to Another in O(n)?
Run a depth-first search from the root to record paths to both the start node and destination node. Compare the paths to find the first position where they differ, which represents the lowest common ancestor. Convert the remaining start path to 'U' moves and append the remaining destination path moves to build the final direction string.
What is the best approach for Step-By-Step Directions From a Binary Tree Node to Another?
The most common approach finds the path from the root to both nodes using DFS, then identifies the lowest common ancestor by comparing the two paths. Replace the remaining steps in the start path with 'U' and append the remaining moves from the destination path. This runs in O(n) time and O(n) space and is typically expected in coding interviews.
Is Step-By-Step Directions From a Binary Tree Node to Another asked at Google/Amazon/Meta?
Binary tree path and lowest common ancestor style problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test DFS traversal, tree path construction, and reasoning about ancestor relationships.
What data structure is used in Step-By-Step Directions From a Binary Tree Node to Another?
The solution primarily uses binary tree traversal with recursion or an explicit stack. Some implementations also maintain arrays for root-to-node paths or a hash map that stores each node's parent to allow upward traversal in the tree.
What is the time complexity of Step-By-Step Directions From a Binary Tree Node to Another?
The optimal solutions run in O(n) time where n is the number of nodes in the binary tree. Each node is visited at most once during DFS traversal. Space complexity is O(n) due to recursion stack, path storage, or the parent map used during traversal.

Ready to solve this problem?

Practice Step-By-Step Directions From a Binary Tree Node to Another with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Paths

Next

Find Distance in a Binary Tree