Balance a binary search tree

Divide and Conquer Greedy Tree Depth-First Search Binary Search Tree Binary Tree

86.3% acceptance

Feb 25, 2026

4160

105

Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them. A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn balance_bst(root: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>) -> Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>> {
    // Collect inorder traversal
    let mut vals = vec![];
    fn inorder(node: Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>>, vals: &mut Vec<i32>) {
      if let Some(n) = node {
        let n = n.borrow();
        inorder(n.left.clone(), vals);
        vals.push(n.val);
        inorder(n.right.clone(), vals);
      }
    }
    inorder(root, &mut vals);
    // Build balanced BST from sorted array
    fn build(vals: &[i32]) -> Option<std::rc::Rc<std::cell::RefCell<crate::TreeNode>>> {
      if vals.is_empty() { return None; }
      let mid = vals.len() / 2;
      let mut node = crate::TreeNode::new(vals[mid]);
      node.left = build(&vals[..mid]);
      node.right = build(&vals[mid+1..]);
      Some(std::rc::Rc::new(std::cell::RefCell::new(node)))
    }
    build(&vals)
  }
}