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.

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

&nbsp;
Example 1:

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.


Example 2:

Input: root = [2,1,3]
Output: [2,1,3]


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 104].
	1 &lt;= Node.val &lt;= 105


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def balanceBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        arr = []
        self.flatTree(root, arr)
        return self.createTree(arr, 0, len(arr))
    
    def flatTree(self, root, arr):
        if not root:
            return
        self.flatTree(root.left, arr)
        arr.append(root)
        self.flatTree(root.right, arr)
    
    def createTree(self, arr, start, length):
        if length == 0:
            return None
        root = arr[start + length / 2]
        root.left = self.createTree(arr, start, length / 2)
        root.right = self.createTree(arr, start + length / 2 + 1, length - length / 2 - 1)
        return root
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> arr = new ArrayList();
        InOrder( root,  arr);
        return sortedArrayToBST( arr, 0, arr.size()-1);
    }
    
    public void InOrder(TreeNode node, List<Integer> arr){
        if(node != null){
            InOrder( node.left, arr);
            arr.add(node.val);
            InOrder( node.right, arr);
        }
    }
    
    public TreeNode sortedArrayToBST(List<Integer> arr, int start, int end) {

        if (start > end) {
            return null;
        }
 
        int mid = (start + end) / 2;
        
        TreeNode node = new TreeNode(arr.get(mid));
        node.left = sortedArrayToBST(arr, start, mid - 1);
        node.right = sortedArrayToBST(arr, mid + 1, end);
         
        return node;
    }
}
class Solution {
public:
    vector<int> nums ;
    void traverse(TreeNode * root){
        if(!root) return ;
        traverse(root->left) ;
        nums.push_back(root->val) ;
        traverse(root->right) ;
        return ;
    }

    TreeNode * makeTree(int s , int e){
        if(s > e) return nullptr ;
        int m = (s + e) / 2 ;
        TreeNode * root = new TreeNode(nums[m]) ;

        root->left = makeTree(s,m - 1) ;
        root->right = makeTree(m + 1,e) ;

        return root ;
    }

    TreeNode* balanceBST(TreeNode* root) {
        traverse(root) ;
        return makeTree(0,size(nums) - 1) ;
    }
};
var balanceBST = function(root) {
let arr = [];//store sorted value in array
let InOrder = (node) => {//inorder helper to traverse and store sorted values in array
    if(!node)
        return;
    InOrder(node.left);
    arr.push(node.val);
    InOrder(node.right);
}
InOrder(root);
let BalancedFromSortedArray = (arr, start, end) => {//create Balanced tree from sorted array
    if(start>end)
        return null;
    let mid = Math.floor((start+end)/2);
    let newNode = new TreeNode(arr[mid]);
    newNode.left = BalancedFromSortedArray(arr,start,mid-1);
    newNode.right = BalancedFromSortedArray(arr,mid+1,end);
    return newNode;
}
let Balanced = BalancedFromSortedArray(arr,0,arr.length-1);
return Balanced;
};
Balance a Binary Search Tree