LeetCode Entry

1382. Balance a Binary Search Tree

09.02.2026 medium 2026 kotlin rust

Balance binary search tree

1382. Balance a Binary Search Tree medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1263

Problem TLDR

Balance binary search tree #medium #dfs

Intuition

Collect to a list with in-order dfs. Build a new, count of left subtree is equal to the count of right subtree. Mid is current.

Approach

• we can store nodes itself on a list
• we can avoid building the list, just make a lazy iterator (sequence in Kotlin, or Stack and from_fn in Rust)

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\), O(log(n)) for the lazy iterator

Code

// 22ms
    fun balanceBST(r: TreeNode?): TreeNode? {
        val l = buildList {fun c(r: TreeNode?) {r?.run { c(left); add(r); c(right) }};c(r)}
        fun b(f: Int, t: Int): TreeNode? =
            if (f > t) null else l[(f+t)/2].apply {
                left = b(f, (f+t)/2-1); right = b((f+t)/2+1, t)
            }
        return b(0, l.lastIndex)
    }

// 0ms
    type Tr = Rc<RefCell<TreeNode>>; type Opt = Option<Tr>;

    pub fn balance_bst(r: Opt) -> Opt {
        fn c(n: &Opt) -> i32 { n.as_ref().map_or(0, |n| 1 + c(&n.borrow().left) + c(&n.borrow().right)) }
        let (n, mut s, mut c) = (c(&r), vec![], r);
        let mut i = std::iter::from_fn(move || {
            while let Some(t) = c.take() { c = t.borrow().left.clone(); s.push(t); }
            s.pop().map(|t| { c = t.borrow().right.clone(); t })
        });
        fn b(k: i32, i: &mut impl Iterator<Item = Tr>) -> Opt {
            if k < 1 { return None }; let l = b(k / 2, i);
            i.next().map(|t| { t.borrow_mut().left = l; t.borrow_mut().right = b(k - 1 - k / 2, i); t })
        }
        b(n, &mut i)
    }