Recover binary search tree

Tree Depth-First Search Binary Search Tree Binary Tree

58.8% acceptance

Feb 27, 2026

8554

289

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

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_tree(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    let mut first: Option<Rc<RefCell<TreeNode>>> = None;
    let mut second: Option<Rc<RefCell<TreeNode>>> = None;
    let mut prev: Option<Rc<RefCell<TreeNode>>> = None;
    
    Self::inorder(root.clone(), &mut first, &mut second, &mut prev);
    
    if let (Some(f), Some(s)) = (first, second) {
      let temp = f.borrow().val;
      f.borrow_mut().val = s.borrow().val;
      s.borrow_mut().val = temp;
    }
  }
  
  fn inorder(
    node: Option<Rc<RefCell<TreeNode>>>,
    first: &mut Option<Rc<RefCell<TreeNode>>>,
    second: &mut Option<Rc<RefCell<TreeNode>>>,
    prev: &mut Option<Rc<RefCell<TreeNode>>>,
  ) {
    if let Some(n) = node {
      Self::inorder(n.borrow().left.clone(), first, second, prev);
      
      if let Some(p) = prev {
        if p.borrow().val > n.borrow().val {
          if first.is_none() {
            *first = Some(p.clone());
          }
          *second = Some(n.clone());
        }
      }
      *prev = Some(n.clone());
      
      Self::inorder(n.borrow().right.clone(), first, second, prev);
    }
  }
}