Binary Search TreesProblem 10 of 22
Convert a normal BST into a Balanced BST
Problem Statement
Given a BST that is not balanced (skewed or unbalanced), convert it into a balanced BST. A balanced BST is one where the height of left and right subtrees of every node differs by at most 1.
Example:
Input (Skewed BST): Output (Balanced BST):
1 3
\ / \
2 2 5
\ / / \
3 1 4 6
\
4
\
5
\
6
Approach 1: Brute Force (Extract and Rebuild)
Intuition
Extract all elements, then build a balanced BST from the sorted array (since inorder of BST is sorted).
Algorithm
- Perform inorder traversal to get sorted array
- Build balanced BST from sorted array using divide and conquer
- Middle element becomes root, recursively build left and right
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root.val);
inorder(root.right, nodes);
}
private TreeNode buildBalancedBST(List<Integer> nodes, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nodes.get(mid));
root.left = buildBalancedBST(nodes, left, mid - 1);
root.right = buildBalancedBST(nodes, mid + 1, right);
return root;
}
public TreeNode balanceBST(TreeNode root) {
List<Integer> nodes = new ArrayList<>();
inorder(root, nodes);
return buildBalancedBST(nodes, 0, nodes.size() - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - Inorder O(n) + Build O(n)
- Space Complexity: O(n) - Storing all nodes
Approach 2: Optimal (Store Node Pointers)
Intuition
Instead of storing just values, store node pointers. This reuses existing nodes instead of creating new ones.
Algorithm
- Inorder traversal to collect node pointers
- Rebuild tree by reassigning left/right pointers
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorderNodes(TreeNode root, List<TreeNode> nodes) {
if (root == null) return;
inorderNodes(root.left, nodes);
nodes.add(root);
inorderNodes(root.right, nodes);
}
private TreeNode buildBalancedFromNodes(List<TreeNode> nodes, int left, int right) {
if (left > right) return null;
int mid = left + (right - left) / 2;
TreeNode root = nodes.get(mid);
root.left = buildBalancedFromNodes(nodes, left, mid - 1);
root.right = buildBalancedFromNodes(nodes, mid + 1, right);
return root;
}
public TreeNode balanceBSTOptimal(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorderNodes(root, nodes);
return buildBalancedFromNodes(nodes, 0, nodes.size() - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass each for inorder and build
- Space Complexity: O(n) - Storing node pointers
Approach 3: DSW Algorithm (Day-Stout-Warren)
Intuition
DSW algorithm converts any BST to a perfectly balanced BST in O(n) time and O(1) extra space. It works in two phases:
- Convert tree to a "vine" (right-skewed tree) using right rotations
- Convert vine to balanced tree using left rotations
Algorithm
- Create a dummy node pointing to root
- Convert to right-leaning vine using right rotations
- Calculate the number of rotations needed
- Perform left rotations in a specific pattern
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void rightRotate(TreeNode parent, TreeNode node) {
TreeNode temp = node.left;
node.left = temp.right;
temp.right = node;
parent.right = temp;
}
private void leftRotate(TreeNode parent, TreeNode node) {
TreeNode temp = node.right;
node.right = temp.left;
temp.left = node;
parent.right = temp;
}
private int treeToVine(TreeNode grand) {
int count = 0;
TreeNode tmp = grand.right;
while (tmp != null) {
if (tmp.left != null) {
rightRotate(grand, tmp);
tmp = grand.right;
} else {
count++;
grand = tmp;
tmp = tmp.right;
}
}
return count;
}
private void vineToTree(TreeNode grand, int n) {
int m = (int) Math.pow(2, Math.floor(Math.log(n + 1) / Math.log(2))) - 1;
// First set of rotations
TreeNode tmp = grand;
for (int i = 0; i < n - m; i++) {
leftRotate(tmp, tmp.right);
tmp = tmp.right;
}
// Remaining rotations
while (m > 1) {
m = m / 2;
tmp = grand;
for (int i = 0; i < m; i++) {
leftRotate(tmp, tmp.right);
tmp = tmp.right;
}
}
}
public TreeNode balanceBSTDSW(TreeNode root) {
if (root == null) return null;
TreeNode grand = new TreeNode(0);
grand.right = root;
int n = treeToVine(grand);
vineToTree(grand, n);
return grand.right;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node rotated at most twice
- Space Complexity: O(1) - In-place algorithm (O(log n) for recursion if used)
Key Takeaways
- Simple approach: Inorder + rebuild is easy to implement and O(n)
- DSW algorithm: In-place O(1) space solution using rotations
- Balanced BST: Height is O(log n), ensuring O(log n) operations
- This is LeetCode #1382 - Balance a Binary Search Tree
- DSW is complex but space-efficient - practical for memory-constrained systems
- The simple approach is preferred in interviews unless space is critical
- Result is not necessarily AVL or Red-Black tree, just height-balanced