Flatten binary tree to linked list

Linked List Stack Tree Depth-First Search Binary Tree

70.3% acceptance

Feb 27, 2026

13613

599

Given the root of a binary tree, flatten the tree into a "linked list": The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

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 flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    use std::collections::VecDeque;
    if root.is_none() {
      return;
    }
    
    let mut stack = VecDeque::new();
    stack.push_back(root.clone().unwrap());
    
    while let Some(node) = stack.pop_back() {
      let mut node_ref = node.borrow_mut();
      let left = node_ref.left.take();
      let right = node_ref.right.take();
      
      if let Some(r) = right {
        stack.push_back(r);
      }
      if let Some(l) = left {
        stack.push_back(l);
      }
      
      node_ref.right = stack.back().cloned();
      node_ref.left = None;
    }
  }
}