🌛Beginner-Friendly Guide 'Balance a Binary Search Tree' - Problem 1382 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:

• The root of an existing Binary Search Tree (BST) that might be unbalanced.

Your goal:

• Return a new, balanced BST containing the exact same node values.
• In the balanced version, the depth of the two subtrees for every node must not differ by more than 1.

Intuition

The most reliable way to balance a tree is to flatten it first. An inorder traversal (Left, Root, Right) of a BST always visits the nodes in sorted order. Once we have a sorted list of all the values, building a balanced tree becomes straightforward.

To build a balanced tree from a sorted list, use a divide‑and‑conquer approach:

1. Pick the middle element of the list as the root. This ensures an equal number of elements fall into the left and right subtrees.
2. Recursively repeat the process for the left half to build the left subtree.
3. Recursively repeat the process for the right half to build the right subtree.

Walkthrough: Understanding the Example

Example 1: root = [1, null, 2, null, 3, null, 4]

1. Flatten: Inorder traversal yields the sorted list [1, 2, 3, 4].
2. Find Middle: The middle index is 1 (value 2). Node 2 becomes the root.
   • Left side: [1] → middle 1 → node 1 becomes the left child of 2.
   • Right side: [3, 4] → middle 3 → node 3 becomes the right child of 2.
   • The remaining value 4 becomes the right child of 3.

The resulting tree is balanced, with no path significantly longer than another.

Code Blocks

C++

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector nums;
        inorder(root, nums);
        return build(nums, 0, nums.size() - 1);
    }

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

    TreeNode* build(const vector& nums, int l, int r) {
        if (l > r) return nullptr;
        int m = l + (r - l) / 2;
        TreeNode* newNode = new TreeNode(nums[m]);
        newNode->left = build(nums, l, m - 1);
        newNode->right = build(nums, m + 1, r);
        return newNode;
    }
};

Python

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        nums = []

        # Step 1: Inorder traversal to get sorted values
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            nums.append(node.val)
            inorder(node.right)

        # Step 2: Build balanced BST from sorted values
        def build(l, r):
            if l > r:
                return None
            m = (l + r) // 2
            node = TreeNode(nums[m])
            node.left = build(l, m - 1)
            node.right = build(m + 1, r)
            return node

        inorder(root)
        return build(0, len(nums) - 1)

JavaScript

var balanceBST = function(root) {
    const nums = [];

    // Step 1: Inorder traversal to get sorted values
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        nums.push(node.val);
        inorder(node.right);
    }

    // Step 2: Build balanced BST from sorted values
    function build(l, r) {
        if (l > r) return null;
        let m = Math.floor((l + r) / 2);
        let node = new TreeNode(nums[m]);
        node.left = build(l, m - 1);
        node.right = build(m + 1, r);
        return node;
    }

    inorder(root);
    return build(0, nums.length - 1);
};

Key Takeaways

• Inorder Traversal: The only traversal that retrieves BST data in natural sorted order.
• Divide and Conquer: Picking the middle element as the root keeps the tree height minimal, ensuring fast operations.
• Tree Transformation: Converting a complex structure to a simpler format (like an array) and rebuilding it can solve many problems efficiently.

Final Thoughts

Balanced trees are the backbone of database indexes and file systems, guaranteeing that lookups remain fast. When an index becomes unbalanced, query times can degrade dramatically. Mastering tree rebalancing is a fundamental skill for building high‑performance software.