> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/balance-a-binary-search-tree.md).

# Balance a Binary Search Tree

Given a binary search tree, return a **balanced** binary search tree with the same node values.

A binary search tree is *balanced* if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/08/22/1515_ex1.png)![](https://assets.leetcode.com/uploads/2019/08/22/1515_ex1_out.png)

```
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,null,null] is also correct.
```

**Constraints:**

* The number of nodes in the tree is between `1` and `10^4`.
* The tree nodes will have distinct values between `1` and `10^5`.

```java
class Solution {
    ArrayList<TreeNode> list;

    public void convertToList(TreeNode root) {
        if (root == null)
            return;
        convertToList(root.left);
        list.add(root);
        convertToList(root.right);
    }

    public TreeNode convertToTree(int start, int end) {
        if (start > end)
            return null;
        int mid = start + (end - start) / 2;
        TreeNode root = list.get(mid);
        root.left = convertToTree(start, mid - 1);
        root.right = convertToTree(mid + 1, end);
        return root;
    }

    public TreeNode balanceBST(TreeNode root) {
        list = new ArrayList<>();
        convertToList(root);
        root = convertToTree(0, list.size() - 1);
        return root;
    }
}
```