Binary tree upside down

Tree Depth-First Search Binary Tree

65.4% acceptance

Mar 31, 2026

305

389

Given the root of a binary tree, turn the tree upside down and return the new root. You can turn a binary tree upside down with the following steps: The original left child becomes the new root. The original root becomes the new right child. The original right child becomes the new left child. The mentioned steps are done level by level. It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.

Solution

Rust

Time O(n)

Space O(1)

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 upside_down_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    let mut cur = root;
    let mut parent: Option<Rc<RefCell<TreeNode>>> = None;
    let mut parent_right: Option<Rc<RefCell<TreeNode>>> = None;
    while let Some(node) = cur {
      let left = node.borrow_mut().left.take();
      let right = node.borrow_mut().right.take();
      node.borrow_mut().left = parent_right;
      node.borrow_mut().right = parent;
      parent = Some(node);
      parent_right = right;
      cur = left;
    }
    parent
  }
}