Serialize and deserialize bst

String Tree Depth-First Search Breadth-First Search Design Binary Search Tree Binary Tree

59.4% acceptance

Jan 13, 2026

3590

180

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;

struct Codec {}

impl Codec {
  fn new() -> Self {
    Codec {}
  }

  fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
    let mut result = Vec::new();
    Self::serialize_helper(&root, &mut result);
    result.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(",")
  }

  fn serialize_helper(node: &Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
    if let Some(n) = node {
      let n = n.borrow();
      result.push(n.val);
      Self::serialize_helper(&n.left, result);
      Self::serialize_helper(&n.right, result);
    }
  }

  fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
    if data.is_empty() {
      return None;
    }
    let vals: Vec<i32> = data.split(',').filter_map(|s| s.parse().ok()).collect();
    Self::deserialize_helper(&vals, i32::MIN, i32::MAX, &mut 0)
  }

  fn deserialize_helper(vals: &[i32], min: i32, max: i32, idx: &mut usize) -> Option<Rc<RefCell<TreeNode>>> {
    if *idx >= vals.len() {
      return None;
    }
    let val = vals[*idx];
    if val < min || val > max {
      return None;
    }
    *idx += 1;
    let mut node = TreeNode::new(val);
    node.left = Self::deserialize_helper(vals, min, val, idx);
    node.right = Self::deserialize_helper(vals, val, max, idx);
    Some(Rc::new(RefCell::new(node)))
  }
}