1382. Balance a Binary Search Tree

MediumView on LeetCode

Tree Binary Search Tree Divide and Conquer Binary Tree

Time: O(n)

Space: O(n)

Intuition

In-order traversal of BST gives sorted array. Build a balanced BST from sorted array (like problem 108).

Algorithm

1In-order traverse to get sorted array.
2Build balanced BST from sorted array: pick middle as root, recurse on halves.

Common Pitfalls

•Two-step: extract sorted array, then rebuild. Can also be done with DSW algorithm in O(1) space.

1382.cs

// Approach: In-order traversal produces a sorted array; recursively build a balanced BST by choosing the mid-point as root.
// Time: O(n) Space: O(n)

public class Solution
        var nums = new List<int>();
        Inorder(root, nums);
        return build(nums, 0, nums.Count - 1);
    }

    private void Inorder(TreeNode root, List<int> nums)
    {
        if (root == null)
            return;

        Inorder(root.left, nums);
        nums.Add(root.val);
        Inorder(root.right, nums);
    }

    private TreeNode build(List<int> nums, int l, int r)
    {
        if (l > r)
            return null;

        int m = (l + r) / 2;
        return new TreeNode(nums[m], build(nums, l, m - 1), build(nums, m + 1, r));
    }
}

Was this solution helpful?