# Balance a Binary Search Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/balance-a-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/balance-a-binary-search-tree
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` of a binary search tree, return _a **balanced** binary search tree with the same node values_. If there is more than one answer, return **any of them**.

A binary search tree is **balanced** if the depth of the two subtrees of every node never differs by more than `1`.

**Example 1:**

![](https://assets.glich.co/dsa/balance-a-binary-search-tree/image0.jpg) 

**Input:** root = [1,null,2,null,3,null,4,null,null]
**Output:** [2,1,3,null,null,null,4]
**Explanation:** This is not the only correct answer, [3,1,4,null,2] is also correct.

**Example 2:**

![](https://assets.glich.co/dsa/balance-a-binary-search-tree/image1.jpg) 

**Input:** root = [2,1,3]
**Output:** [2,1,3]

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `1 <= Node.val <= 105`

# Approaches
## Build a Self-Balancing Tree (e.g., AVL)
This approach simulates the behavior of a self-balancing Binary Search Tree, such as an AVL tree or a Red-Black tree. The core idea is to extract all the node values from the given unbalanced tree and then insert them one by one into a new tree structure that maintains its balance automatically after each insertion. While conceptually straightforward if a self-balancing tree library is available, implementing it from scratch is complex and less efficient time-wise compared to other methods.
**Time:** O(N log N), where N is the number of nodes. Traversing the original tree is O(N). We then perform N insertions into a tree that grows up to size N. Each insertion into a self-balancing tree takes O(log k) time, where k is the current size of the tree. The total time for N insertions is Σ(log k) for k=1 to N, which is O(N log N). · **Space:** O(N). We need O(N) space to store the node values in a list. Additionally, the new tree itself requires O(N) space for its nodes. The recursion stack for insertions will take O(log N) space.
**Pros:** The logic is straightforward if one has access to a pre-built self-balancing tree data structure.
**Cons:** Worse time complexity (O(N log N)) compared to the optimal O(N) solution.; Implementing a self-balancing tree from scratch is complex, verbose, and prone to errors.
### Explanation
The algorithm proceeds in two main phases:

1.  **Node Value Extraction:** Traverse the input tree using any standard traversal method (like pre-order, in-order, or level-order) to collect all node values into a list.
2.  **Incremental Construction:** Create a new, initially empty, BST. Iterate through the collected values and insert each one into this new tree. The key is that the insertion logic must include a balancing step. For instance, in an AVL tree, after a standard BST insertion, we would trace back up to the root, checking the balance factor at each node and performing single or double rotations if the tree becomes unbalanced.

This process ensures that after all N nodes are inserted, the resulting tree is guaranteed to be balanced. However, the cost of rebalancing at each step accumulates, leading to a higher overall time complexity.

```java
// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    int height; // Extra field for AVL tree
    TreeNode(int val) { this.val = val; this.height = 1; }
}

class Solution {
    // Helper to get height
    private int height(TreeNode N) {
        if (N == null) return 0;
        return N.height;
    }

    // Helper to get balance factor
    private int getBalance(TreeNode N) {
        if (N == null) return 0;
        return height(N.left) - height(N.right);
    }

    // Right rotate
    private TreeNode rightRotate(TreeNode y) { /* ... AVL rotation logic ... */ return new_root; }

    // Left rotate
    private TreeNode leftRotate(TreeNode x) { /* ... AVL rotation logic ... */ return new_root; }

    // AVL insert function
    private TreeNode insert(TreeNode node, int val) {
        // 1. Standard BST insertion
        if (node == null) return new TreeNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        else return node; // Duplicate values are not inserted

        // 2. Update height of this ancestor node
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 3. Get the balance factor to check for unbalance
        int balance = getBalance(node);

        // 4. If unbalanced, perform rotations
        // Left Left Case
        if (balance > 1 && val < node.left.val) return rightRotate(node);
        // Right Right Case
        if (balance < -1 && val > node.right.val) return leftRotate(node);
        // Left Right Case
        if (balance > 1 && val > node.left.val) { /* ... */ }
        // Right Left Case
        if (balance < -1 && val < node.right.val) { /* ... */ }

        return node;
    }

    private void inorderTraversal(TreeNode root, List<Integer> nodes) {
        if (root == null) return;
        inorderTraversal(root.left, nodes);
        nodes.add(root.val);
        inorderTraversal(root.right, nodes);
    }

    public TreeNode balanceBST(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        inorderTraversal(root, nodes); // Get all nodes

        TreeNode newRoot = null;
        for (int val : nodes) {
            newRoot = insert(newRoot, val); // Insert into AVL tree
        }
        return newRoot;
    }
}
```
### Algorithm
- Create a list to store node values.
- Traverse the input BST to populate the list with all node values.
- Initialize a new `root` to `null`.
- For each value in the list, insert it into the new tree using a self-balancing insertion algorithm (like AVL insert).
- The AVL insertion performs a standard BST insert, then updates heights and performs rotations if necessary to maintain balance.
- Return the `root` of the newly constructed balanced tree.

## In-order Traversal and Reconstruction from Sorted Array
This is the most common and highly intuitive approach for this problem. It beautifully utilizes a fundamental property of Binary Search Trees: an in-order traversal of a BST yields its elements in sorted order. The solution is a clean two-step process: first, flatten the tree into a sorted array of values, and second, construct a new, perfectly balanced BST from this sorted array.
**Time:** O(N), where N is the number of nodes. The in-order traversal visits each node once, taking O(N) time. Building the balanced BST from the sorted list also processes each element once, taking another O(N) time. The total time is O(N) + O(N) = O(N). · **Space:** O(N). The primary space cost is the list used to store the N node values. The recursion stack for the building process will have a maximum depth of O(log N) since the array is split in half at each step. Therefore, the space complexity is dominated by the list, resulting in O(N).
**Pros:** Optimal time complexity of O(N).; The logic is relatively simple, easy to understand, and implement.; It's a very common and standard pattern for problems involving BSTs and sorted arrays.
**Cons:** Requires O(N) extra space to store the intermediate list of nodes, which can be significant for very large trees under strict memory constraints.
### Explanation
The algorithm is divided into two main parts:

1.  **In-order Traversal:** We traverse the given BST using an in-order traversal. This is a recursive process where we first visit the left subtree, then the node itself, and finally the right subtree. By doing this, we collect all the node values into a list, which will naturally be sorted in ascending order.

2.  **Build Balanced BST from Sorted Array:** With the sorted list of values, we can now build a balanced BST. The key to keeping it balanced is to always choose the middle element of the current array (or sub-array) as the root of the tree (or subtree). The elements to the left of the middle element will form the left subtree, and the elements to the right will form the right subtree. We apply this logic recursively.

This method guarantees a tree where the depth of the two subtrees of every node never differs by more than one.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        // Step 1: Perform in-order traversal to get sorted node values
        List<Integer> sortedNodes = new ArrayList<>();
        inorderTraversal(root, sortedNodes);

        // Step 2: Build a balanced BST from the sorted list
        return buildBalancedBST(sortedNodes, 0, sortedNodes.size() - 1);
    }

    // Helper function for in-order traversal
    private void inorderTraversal(TreeNode node, List<Integer> sortedNodes) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left, sortedNodes);
        sortedNodes.add(node.val);
        inorderTraversal(node.right, sortedNodes);
    }

    // Helper function to build a balanced BST from a sorted list
    private TreeNode buildBalancedBST(List<Integer> nodes, int start, int end) {
        // Base case
        if (start > end) {
            return null;
        }

        // Find the middle element to make it the root
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nodes.get(mid));

        // Recursively build the left and right subtrees
        root.left = buildBalancedBST(nodes, start, mid - 1);
        root.right = buildBalancedBST(nodes, mid + 1, end);

        return root;
    }
}
```
### Algorithm
- **Step 1: In-order Traversal**
  - Create an empty list to store node values.
  - Define a recursive helper `inorder(node, list)`.
  - In the helper, recursively traverse the left subtree, add the current node's value to the list, and then recursively traverse the right subtree.
  - Call this helper on the root to populate the list with sorted values.
- **Step 2: Build Balanced BST**
  - Define a recursive helper `build(list, start, end)`.
  - If `start > end`, return `null` (base case).
  - Find the middle index `mid = start + (end - start) / 2`.
  - Create a new `TreeNode` with the value at `list.get(mid)`. This is the root of the current subtree.
  - Recursively set the left child: `root.left = build(list, start, mid - 1)`.
  - Recursively set the right child: `root.right = build(list, mid + 1, end)`.
  - Return the `root`.

## In-Place Balancing via Day-Stout-Warren (DSW) Algorithm
The Day-Stout-Warren (DSW) algorithm is a highly efficient but complex method for balancing a Binary Search Tree. Its main advantage is that it performs the balancing in-place, meaning it restructures the existing nodes without allocating O(N) extra space for an intermediate data structure. It achieves O(N) time and O(1) auxiliary space (if implemented iteratively). The algorithm works in two major phases: converting the tree into a 'vine' (a skewed list) and then converting the vine into a balanced tree through a series of carefully orchestrated rotations.
**Time:** O(N). The tree-to-vine phase involves a constant number of pointer changes per edge, resulting in O(N) time. The vine-to-tree phase also performs a total of O(N) rotations. Thus, the overall time complexity is linear. · **Space:** O(1) for an iterative implementation. The algorithm works by rearranging pointers of the existing nodes (in-place) and does not require auxiliary storage proportional to the number of nodes. If recursion is used for rotations, the space could be O(H) where H is the height of the tree, which is O(N) in the worst case before balancing.
**Pros:** Extremely space-efficient, using O(1) or O(log N) auxiliary space.; Optimal time complexity of O(N).
**Cons:** Significantly more complex to understand, implement, and debug compared to the array-based approach.; The logic involving multiple passes and calculated rotations is non-trivial and error-prone.
### Explanation
The DSW algorithm is a two-pass procedure over the tree nodes.

1.  **Tree-to-Vine (Backbone Creation):** The first phase transforms the arbitrary BST into a sorted, linked-list-like structure called a 'vine' or 'backbone'. This is a tree where every node's left child is `null`. This is achieved by repeatedly applying right rotations. We traverse the tree, and whenever a node has a left child, we perform a right rotation at that node to make the left child its parent. This process is repeated until the node has no left child, and then we move down to its right child.

2.  **Vine-to-Tree (Balancing):** The second phase converts the vine back into a perfectly balanced BST. This is done by performing a calculated number of left rotations. The vine is traversed, and left rotations are applied at every other node. This process is repeated in passes, each time halving the number of rotations, until the tree is balanced. The number of rotations in each pass is calculated based on the total number of nodes to ensure the final structure is as compact as possible.

Due to its complexity, this algorithm is more of an academic interest and is rarely expected in a general coding interview, but it represents the most space-efficient solution.

```java
class Solution {
    // Helper to perform a right rotation on a node's parent
    private TreeNode rightRotate(TreeNode parent, TreeNode child) {
        // ... implementation of right rotation ...
        // Returns the new root of the rotated subtree
    }

    // Helper to perform a left rotation on a node's parent
    private TreeNode leftRotate(TreeNode parent, TreeNode child) {
        // ... implementation of left rotation ...
        // Returns the new root of the rotated subtree
    }

    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;

        // Create a pseudo-root to simplify rotations at the main root
        TreeNode pseudoRoot = new TreeNode(0);
        pseudoRoot.right = root;

        // 1. Tree-to-Vine phase
        TreeNode current = pseudoRoot;
        int nodeCount = 0;
        while (current.right != null) {
            if (current.right.left != null) {
                // Right rotate to flatten the left subtree
                TreeNode oldRight = current.right;
                TreeNode newRight = oldRight.left;
                oldRight.left = newRight.right;
                newRight.right = oldRight;
                current.right = newRight;
            } else {
                // Move to the next node in the vine
                nodeCount++;
                current = current.right;
            }
        }

        // 2. Vine-to-Tree phase
        int m = (int) Math.pow(2, Math.floor(Math.log(nodeCount + 1) / Math.log(2))) - 1;
        
        // Perform n - m initial left rotations
        current = pseudoRoot;
        for (int i = 0; i < nodeCount - m; i++) {
            TreeNode oldRight = current.right;
            TreeNode newRight = oldRight.right;
            oldRight.right = newRight.left;
            newRight.left = oldRight;
            current.right = newRight;
            current = current.right;
        }

        // Perform remaining left rotations in passes
        while (m > 1) {
            m /= 2;
            current = pseudoRoot;
            for (int i = 0; i < m; i++) {
                TreeNode oldRight = current.right;
                TreeNode newRight = oldRight.right;
                oldRight.right = newRight.left;
                newRight.left = oldRight;
                current.right = newRight;
                current = current.right;
            }
        }

        return pseudoRoot.right;
    }
}
```
### Algorithm
- **Phase 1: Tree-to-Vine**
  - Create a pseudo-root to simplify operations.
  - Traverse the tree. At each node, as long as it has a left child, perform right rotations to eliminate the left branch, effectively making the tree a straight line to the right (a vine).
  - Count the number of nodes (`n`) during this process.
- **Phase 2: Vine-to-Tree**
  - Calculate the number of nodes `m` for the largest possible complete binary tree with `n` nodes.
  - Perform `n - m` left rotations on the first `n - m` nodes of the vine to compress the initial part of the vine.
  - In a loop, repeatedly halve `m` and perform `m` left rotations on the vine. This builds up the balanced tree layer by layer from the compressed vine.
- Return the new root of the balanced tree.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private List < Integer > nums = new ArrayList <>(); public TreeNode balanceBST ( TreeNode root ) { dfs ( root ); return build ( 0 , nums . size () - 1 ); } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); nums . add ( root . val ); dfs ( root . right ); } private TreeNode build ( int i , int j ) { if ( i > j ) { return null ; } int mid = ( i + j ) >> 1 ; TreeNode left = build ( i , mid - 1 ); TreeNode right = build ( mid + 1 , j ); return new TreeNode ( nums . get ( mid ), left , right ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * balanceBST ( TreeNode * root ) { dfs ( root ); return build ( 0 , nums . size () - 1 ); } private: vector < int > nums ; void dfs ( TreeNode * root ) { if ( ! root ) { return ; } dfs ( root -> left ); nums . push_back ( root -> val ); dfs ( root -> right ); } TreeNode * build ( int i , int j ) { if ( i > j ) { return nullptr ; } int mid = ( i + j ) >> 1 ; TreeNode * left = build ( i , mid - 1 ); TreeNode * right = build ( mid + 1 , j ); return new TreeNode ( nums [ mid ], left , right ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def balanceBST ( self , root : TreeNode ) -> TreeNode : def dfs ( root : TreeNode ): if root is None : return dfs ( root . left ) nums . append ( root . val ) dfs ( root . right ) def build ( i : int , j : int ) -> TreeNode : if i > j : return None mid = ( i + j ) >> 1 left = build ( i , mid - 1 ) right = build ( mid + 1 , j ) return TreeNode ( nums [ mid ], left , right ) nums = [] dfs ( root ) return build ( 0 , len ( nums ) - 1 )
```