LeetCode Entry

1382. Balance a Binary Search Tree

26.06.2024 medium 2024 kotlin rust

Make a balanced Binary Search Tree

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

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/651

Problem TLDR

Make a balanced Binary Search Tree #medium

Intuition

Construct it back from a sorted array: always peek the middle.

Approach

• notice how slices in Rust are helping to reduce the complexity

Complexity

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

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

Code

    fun balanceBST(root: TreeNode?): TreeNode? {
        val sorted = mutableListOf<Int>()
        fun dfs1(n: TreeNode?): Unit? = n?.run {
            dfs1(left); sorted += `val`; dfs1(right) }
        fun dfs2(lo: Int, hi: Int): TreeNode? =
            if (lo > hi) null else {
            val mid = (lo + hi) / 2
            TreeNode(sorted[mid]).apply {
                left = dfs2(lo, mid - 1); right = dfs2(mid + 1, hi)
            }}
        dfs1(root); return dfs2(0, sorted.lastIndex)
    }

    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs1(n: &Option<Rc<RefCell<TreeNode>>>, sorted: &mut Vec<i32>) {
            let Some(n) = n.as_ref() else { return; }; let n = n.borrow();
            dfs1(&n.left, sorted); sorted.push(n.val); dfs1(&n.right, sorted)
        }
        fn dfs2(sorted: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
            if sorted.len() < 1 { return None }; let mid = sorted.len() / 2;
            let left = dfs2(&sorted[..mid]);
            let right = dfs2(&sorted[mid + 1..]);
            Some(Rc::new(RefCell::new(TreeNode { val: sorted[mid], left: left, right: right })))
        }
        let mut sorted = vec![]; dfs1(&root, &mut sorted); dfs2(&sorted[..])
    }