1382.md

1382. Balance a Binary Search Tree

Level:

Topic:

Similar Problem:

• 108. Convert Sorted Array to Binary Search Tree

Question

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.

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

Intuition

Recursive:

• inorder traversal of BST is already sorted
• store all value in the sorted list
• use the list to build a BST based on the mid position of the unbuild values (the root node value is always the middle value of the list)

Code

Time: O(n)
Space: O(n)

Recursive

List<Integer> list = new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
    inorder(root);
    return build(0, list.size()-1);
}

private TreeNode build(int low, int high) {
    // low == high is the last node to be inserted
    if (low > high)
        return null;

    int mid = low + (high-low)/2;
    TreeNode root = new TreeNode(list.get(mid));
    root.left = build(low, mid-1);
    root.right = build(mid+1, high);
    return root;
}


private void inorder(TreeNode root) {
    if (root == null)
        return;
    inorder(root.left);
    list.add(root.val);
    inorder(root.right);
}