Tejav
#2096

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

Medium
StringTreeDepth-First SearchBinary TreeDepth-First Search (DFS)Lowest Common Ancestor (LCA)Tree Traversal
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(h)
💡

Intuition

Time O(n)Space O(h)

Instead of finding paths separately, we can find the LCA directly and then construct the path from s to t using the LCA. This reduces redundant work and improves efficiency.

⚙️

Algorithm

3 steps
  1. 1Step 1: Use DFS to find the LCA of the start and destination nodes.
  2. 2Step 2: Construct the path from the start node to the LCA by moving up to the parent nodes.
  3. 3Step 3: Construct the path from the LCA to the destination node by moving down to the child nodes.
solution.py37 lines
1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def getDirections(self, root: TreeNode, startValue: int, destValue: int) -> str:
9        self.lca = None
10        self.dfs(root, startValue, destValue)
11        path = []
12        self.path_to_lca(root, startValue, path)
13        path_to_dest = []
14        self.path_to_lca(root, destValue, path_to_dest)
15        up_moves = len(path) - 1
16        return 'U' * up_moves + 'L' * (len(path_to_dest) - 1) + 'R' * (len(path_to_dest) - 1)
17
18    def dfs(self, node, startValue, destValue):
19        if not node:
20            return False
21        left = self.dfs(node.left, startValue, destValue)
22        right = self.dfs(node.right, startValue, destValue)
23        mid = node.val == startValue or node.val == destValue
24        if mid + left + right >= 2:
25            self.lca = node
26        return mid or left or right
27
28    def path_to_lca(self, node, value, path):
29        if not node:
30            return False
31        path.append(node.val)
32        if node.val == value:
33            return True
34        if self.path_to_lca(node.left, value, path) or self.path_to_lca(node.right, value, path):
35            return True
36        path.pop()
37        return False
ℹ

Complexity note: The time complexity is O(n) because we traverse the tree once to find the LCA and once more to construct the path. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

  • 1The shortest path between two nodes in a tree always passes through their Lowest Common Ancestor (LCA).
  • 2Finding paths separately can lead to redundant calculations; finding the LCA first is more efficient.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.