Balance a Binary Search Tree

February 9th, 2026

Description

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.

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]

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
1 <= Node.val <= 10⁵

Solutions

This is an optimized version that collects nodes via in-order traversal into a sorted array, then recursively reconstructs the tree using a divide-and-conquer approach where each subtree's root is the middle element of its range. Unlike the previous version, it skips the step of clearing node pointers during traversal, making it slightly more efficient while achieving the same balanced tree structure.

Language: javascript(2026-02-09 10:14)DONE

CPU Performance76.47%

Memory Performance84.71%

/**
 * 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 nodes = [];

    const dfs = (node) => {
        if (!node) return;

        dfs(node.left);
        nodes.push(node);
        dfs(node.right);
    };
    dfs(root);

    const createBalancedBST = (from, to) => {
        if (from > to) return null;

        const pos = Math.floor((from + to) / 2);

        nodes[pos].left = createBalancedBST(from, pos - 1);
        nodes[pos].right = createBalancedBST(pos + 1, to);

        return nodes[pos];
    };

    return createBalancedBST(0, nodes.length - 1);
};

Description

Solutions

AI Explanation