Step by step directions from a binary tree node to another

String Tree Depth-First Search Binary Tree

56.4% acceptance

Feb 25, 2026

3248

170

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

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn get_directions(root: Option<Rc<RefCell<TreeNode>>>, start_value: i32, dest_value: i32) -> String {
    // Find path from root to start_value and root to dest_value
    fn find_path(node: &Option<Rc<RefCell<TreeNode>>>, target: i32, path: &mut Vec<char>) -> bool {
      match node {
        None => false,
        Some(n) => {
          let n = n.borrow();
          if n.val == target {
            return true;
          }
          path.push('L');
          if find_path(&n.left, target, path) {
            return true;
          }
          path.pop();
          path.push('R');
          if find_path(&n.right, target, path) {
            return true;
          }
          path.pop();
          false
        }
      }
    }

    let mut path_start = Vec::new();
    let mut path_dest = Vec::new();
    find_path(&root, start_value, &mut path_start);
    find_path(&root, dest_value, &mut path_dest);

    // Remove common prefix (LCA path)
    let common = path_start.iter().zip(path_dest.iter())
      .take_while(|(a, b)| a == b)
      .count();

    // Result: go up from start to LCA, then down to dest
    let ups = path_start.len() - common;
    let mut result: String = std::iter::repeat('U').take(ups).collect();
    result.extend(&path_dest[common..]);
    result
  }
}