Recover a tree from preorder traversal

String Tree Depth-First Search Binary Tree

83.2% acceptance

Feb 27, 2026

2288

We run a preorder depth-first search (DFS) on the root of a binary tree. At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0. If a node has only one child, that child is guaranteed to be the left child. Given the output traversal of this traversal, recover the tree and return its root.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn recover_from_preorder(traversal: String) -> Option<Rc<RefCell<TreeNode>>> {
    let s = traversal.as_bytes();
    let mut i = 0;
    let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
    while i < s.len() {
      let mut depth = 0;
      while i < s.len() && s[i] == b'-' { depth += 1; i += 1; }
      let mut val = 0i32;
      while i < s.len() && s[i].is_ascii_digit() { val = val*10 + (s[i]-b'0') as i32; i += 1; }
      while stack.len() > depth { stack.pop(); }
      let node = Rc::new(RefCell::new(TreeNode::new(val)));
      if let Some(parent) = stack.last() {
        if parent.borrow().left.is_none() { parent.borrow_mut().left = Some(node.clone()); }
        else { parent.borrow_mut().right = Some(node.clone()); }
      }
      stack.push(node);
    }
    stack.first().map(|n| n.clone())
  }
}