Balance a Binary Search Tree

Link: LeetCode - Balance a Binary Search Tree

Problem Statement

Given the root of a Binary Search Tree (BST), return a balanced BST with the same node values.
A BST is balanced if the depth of the two subtrees of every node never differs by more than 1.

Example

Input:

       1
        \
         2
          \
           3
            \
             4

Output:

       2
      / \
     1   3
            \
             4

Constraints

• The number of nodes in the tree is in the range [1, 10⁴].

• 1 <= Node.val <= 10⁵

Intuition

An unbalanced BST may look like a skewed list, which leads to inefficient O(N) operations.
To balance it:

1. Use in-order traversal to get a sorted array of values.

2. Build a balanced BST from that array using a divide-and-conquer approach (like constructing a BST from sorted array).

Approach

1. Inorder Traversal → Get sorted list of node values.

2. Build Balanced BST from sorted list (middle becomes root recursively).

Java Code

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        getInorder(root, inorder);
        return buildBalancedTree(inorder, 0, inorder.size() - 1);
    }

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

    private TreeNode buildBalancedTree(List<Integer> inorder, int start, int end) {
        if (start > end) return null;

        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(inorder.get(mid));

        node.left = buildBalancedTree(inorder, start, mid - 1);
        node.right = buildBalancedTree(inorder, mid + 1, end);

        return node;
    }
}

Time & Space Complexity

• Time Complexity: O(N)

  • O(N) for inorder traversal

  • O(N) for constructing the tree

• Space Complexity:

  • O(N) for storing inorder list

  • O(H) recursion stack (O(log N) if tree is balanced)

Dry Run

Unbalanced BST:

    1
     \
      2
       \
        3
         \
          4

Inorder: [1, 2, 3, 4]
Balanced Tree:

     2
    / \
   1   3
          \
           4

Conclusion

This problem is a classic example of:

• Reconstructing balanced BSTs.

• Leveraging inorder traversal.

• Divide-and-conquer recursion.