1382. Balance a Binary Search Tree

Intuition

To balance a binary search tree (BST), we need to ensure that the depth of the two subtrees of every node never differs by more than one. The best way to achieve this is to use the properties of BSTs and sorted arrays. An inorder traversal of a BST yields a sorted array. By using this sorted array, we can recursively construct a balanced BST.

Approach

1. Inorder Traversal: - Perform an inorder traversal of the given BST to collect the node values in a sorted array. This traversal ensures that we process the nodes in ascending order.
2. Construct Balanced BST: - Use the sorted array to construct a balanced BST. The middle element of the array becomes the root of the BST. Recursively, the left half of the array will form the left subtree and the right half will form the right subtree. - This recursive splitting ensures that the tree remains balanced, as each subtree will have a similar number of nodes.
3. Implementation: - Implement two helper functions: - inorder: Collects the nodes in an inorder traversal. - buildBalancedBST: Recursively constructs the balanced BST from the sorted array.

Complexity

Time Complexity:

• The inorder traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the tree.
• Constructing the balanced BST from the sorted array also takes \(O(n)\) time, as each element is processed once.
• Therefore, the overall time complexity is \(O(n)\).

Space Complexity:

• The space complexity is \(O(n)\) for storing the sorted array of node values.
• Additionally, the recursion stack for constructing the balanced BST takes \(O(log n)\) space in the average case (for a balanced BST) and \(O(n)\) space in the worst case (for a completely unbalanced BST).
• Therefore, the overall space complexity is \(O(n)\).

Code Explanation

This document explains the code for balancing a binary search tree (BST) using JavaScript, function by function.

Inorder Traversal

The inorder function performs an inorder traversal of the binary tree and stores the nodes in an array. Inorder traversal processes nodes in ascending order for a BST.

var inorder = function (root, nodes) {
    if (root === null) return;
    inorder(root.left, nodes);
    nodes.push(root);
    inorder(root.right, nodes);
}

• Parameters: - root: The root of the binary tree. - nodes: An array to store the nodes in sorted order.
• Process: - If the current node (root) is null, return immediately. - Recursively traverse the left subtree. - Add the current node to the array nodes. - Recursively traverse the right subtree.

Constructing a Balanced BST

The solve function constructs a balanced BST from a sorted array of nodes.

var solve = function (nodes, start, end) {
    if (end < start) return null;
    const mid = Math.floor((end - start) / 2) + start;
    const root = nodes[mid];
    root.left = solve(nodes, start, mid - 1);
    root.right = solve(nodes, mid + 1, end);
    return root;
}

• Parameters: - nodes: The sorted array of nodes. - start: The start index for the current subtree. - end: The end index for the current subtree.
• Process: - If start is greater than end, return null (base case). - Calculate the middle index (mid) of the current subtree. - The node at mid becomes the root of the current subtree. - Recursively construct the left subtree using the left half of the array. - Recursively construct the right subtree using the right half of the array. - Return the constructed subtree rooted at root.

Balancing the BST

The balanceBST function balances an unbalanced BST.

var balanceBST = function (root) {
    if (root === null) return null;
    const inorderTraversal = [];
    inorder(root, inorderTraversal);
    return solve(inorderTraversal, 0, inorderTraversal.length - 1);
}

• Parameters: - root: The root of the unbalanced BST.
• Process: - If root is null, return null. - Perform an inorder traversal of the BST to get the nodes in sorted order. - Use the solve function to construct a balanced BST from the sorted array of nodes. - Return the root of the balanced BST.

Conclusion

The provided code efficiently balances an unbalanced BST by utilizing the properties of inorder traversal and sorted arrays. The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of nodes in the tree.

Code

C++

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        if (root == nullptr) return nullptr;
        vector inorderTraversal;
        inorder(root, inorderTraversal);
        return solve(inorderTraversal, 0, inorderTraversal.size() - 1);
    }

private:
    void inorder(TreeNode* root, vector& nodes) {
        if (root == nullptr) return;
        inorder(root->left, nodes);
        nodes.push_back(root);
        inorder(root->right, nodes);
    }

    TreeNode* solve(const vector& nodes, int start, int end) {
        if (end < start) return nullptr;
        int mid = start + (end - start) / 2;
        TreeNode* root = nodes[mid];
        root->left = solve(nodes, start, mid - 1);
        root->right = solve(nodes, mid + 1, end);
        return root;
    }
};

Python

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        inorder_traversal = []
        self.inorder(root, inorder_traversal)
        return self.solve(inorder_traversal, 0, len(inorder_traversal) - 1)

    def inorder(self, root: TreeNode, nodes: list) -> None:
        if root is None:
            return
        self.inorder(root.left, nodes)
        nodes.append(root)
        self.inorder(root.right, nodes)

    def solve(self, nodes: list, start: int, end: int) -> TreeNode:
        if start > end:
            return None
        mid = (start + end) // 2
        root = nodes[mid]
        root.left = self.solve(nodes, start, mid - 1)
        root.right = self.solve(nodes, mid + 1, end)
        return root

Java

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;
        List inorderTraversal = new ArrayList<>();
        inorder(root, inorderTraversal);
        return solve(inorderTraversal, 0, inorderTraversal.size() - 1);
    }

    private void inorder(TreeNode root, List nodes) {
        if (root == null) return;
        inorder(root.left, nodes);
        nodes.add(root);
        inorder(root.right, nodes);
    }

    private TreeNode solve(List nodes, int start, int end) {
        if (end < start) return null;
        int mid = (end - start) / 2 + start;
        TreeNode root = nodes.get(mid);
        root.left = solve(nodes, start, mid - 1);
        root.right = solve(nodes, mid + 1, end);
        return root;
    }
}

JavaScript

/**
 * @param {TreeNode} root
 * @param {TreeNode[]} nodes
 */
var inorder = function (root, nodes) {
    if (root === null) return;
    inorder(root.left, nodes);
    nodes.push(root);
    inorder(root.right, nodes);
}

/**
 * @param {TreeNode[]} nodes
 * @param {number} start
 * @param {number} end
 * @returns {TreeNode|null}
 */
var solve = function (nodes, start, end) {
    if (end < start) return null;
    const mid = Math.floor((end - start) / 2) + start;
    const root = nodes[mid];
    root.left = solve(nodes, start, mid - 1);
    root.right = solve(nodes, mid + 1, end);
    return root;
}

/**
 * @param {TreeNode} root
 * @returns {TreeNode|null}
 */
var balanceBST = function (root) {
    if (root === null) return null;
    const inorderTraversal = [];
    inorder(root, inorderTraversal);
    return solve(inorderTraversal, 0, inorderTraversal.length - 1);
}