1382. Balance a Binary Search Tree

/**
 * Problem: LeetCode 1382 - Balance a Binary Search Tree
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> sortedVals = new ArrayList<>();
        inorder(root, sortedVals);
        return buildBalancedBST(sortedVals, 0, sortedVals.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> sortedVals) {
        if (node == null) {
            return;
        }
        inorder(node.left, sortedVals);
        sortedVals.add(node.val);
        inorder(node.right, sortedVals);
    }

    private TreeNode buildBalancedBST(List<Integer> sortedVals, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(sortedVals.get(mid));
        node.left = buildBalancedBST(sortedVals, left, mid - 1);
        node.right = buildBalancedBST(sortedVals, mid + 1, right);

        return node;
    }
}

"""
Problem: LeetCode 1382 - Balance a Binary Search Tree
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        sorted_vals: List[int] = []

        def inorder(node: Optional[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left)
            sorted_vals.append(node.val)
            inorder(node.right)

        inorder(root)

        def build_balanced_bst(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            mid = left + (right - left) // 2
            node = TreeNode(sorted_vals[mid])
            node.left = build_balanced_bst(left, mid - 1)
            node.right = build_balanced_bst(mid + 1, right)
            return node

        return build_balanced_bst(0, len(sorted_vals) - 1)

/**
 * Problem: LeetCode 1382 - Balance a Binary Search Tree
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> sortedVals;
        inorder(root, sortedVals);
        return buildBalancedBST(sortedVals, 0, sortedVals.size() - 1);
    }

private:
    void inorder(TreeNode* node, vector<int>& sortedVals) {
        if (!node) {
            return;
        }
        inorder(node->left, sortedVals);
        sortedVals.push_back(node->val);
        inorder(node->right, sortedVals);
    }

    TreeNode* buildBalancedBST(const vector<int>& sortedVals, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(sortedVals[mid]);
        node->left = buildBalancedBST(sortedVals, left, mid - 1);
        node->right = buildBalancedBST(sortedVals, mid + 1, right);

        return node;
    }
};

/**
 * Problem: LeetCode 1382 - Balance a Binary Search Tree
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var balanceBST = function(root) {
    const sortedVals = [];

    const inorder = function(node) {
        if (!node) return;
        inorder(node.left);
        sortedVals.push(node.val);
        inorder(node.right);
    };

    inorder(root);

    const buildBalancedBST = function(left, right) {
        if (left > right) return null;

        const mid = left + Math.floor((right - left) / 2);
        const node = new TreeNode(sortedVals[mid]);
        node.left = buildBalancedBST(left, mid - 1);
        node.right = buildBalancedBST(mid + 1, right);

        return node;
    };

    return buildBalancedBST(0, sortedVals.length - 1);
};