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

Binary Search Trees are powerful data structures, but their efficiency relies entirely on their shape. When a tree becomes too "skewed" or tall, it loses its performance benefits and starts acting like a slow linked list. This guide will show you how to take any lopsided tree and rebuild it into a perfectly balanced masterpiece.

---

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. A key property of a Binary Search Tree is that an Inorder Traversal (Left, Root, Right) always visits the nodes in sorted order. Once we have a sorted list of all the values, the problem becomes much simpler.

To build a balanced tree from a sorted list, we use a "Divide and Conquer" approach:

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

---

Walkthrough: Understanding the Examples

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

1. Flatten: We perform an inorder traversal. The resulting sorted list is [1, 2, 3, 4].
2. Find Middle: The middle index of [1, 2, 3, 4] is index 1 (value 2). Node 2 becomes our root.
3. Split:
4. Left side: [1]. The middle is 1. Node 1 becomes the left child of 2.

5. Right side: [3, 4]. The middle is 3. Node 3 becomes the right child of 2.

6. Final Split: The remaining value 4 becomes the right child of 3.

7. Result: We now have a balanced tree where no path is significantly longer than another.

---

Code Blocks

C++

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

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

    TreeNode* build(const vector<int>& 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.push(node.val)); // Note: simple push is used here
        inorder(node.right);
    }

    // Explicitly using a helper to collect values
    const collect = (node) => {
        if (!node) return;
        collect(node.left);
        nums.push(node.val);
        collect(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;
    }

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

---

Key Takeaways

• Inorder Traversal: This is the "secret sauce" for BSTs. It is the only traversal that retrieves data in its natural sorted order.
• Divide and Conquer: By always picking the middle element as the root, we ensure the tree height stays , which keeps operations fast.
• Tree Transformation: Complex problems can often be solved by converting a data structure into a simpler format (like an array) and then rebuilding it.

---

Final Thoughts

In the real world, database indexes and file systems rely on balanced trees to ensure that looking up a record takes a fraction of a second rather than minutes. If a database index becomes unbalanced, query times can skyrocket. Understanding how to rebalance structures is a fundamental skill for high-performance software engineering.