Balance a Binary Search Tree

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:

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:

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

Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. 1 <= Node.val <= 10<sup>5</sup>

## Balanced Binary Search Tree

This problem requires us to take the root of a binary search tree (BST) and return a balanced binary search tree with the same node values. A balanced BST is defined as a tree where the depth of the two subtrees of every node never differs by more than 1. There might be multiple valid balanced BSTs, and we can return any of them.

### 1. Naive Approach (Inorder Traversal and Rebuild)

The naive approach involves extracting all the node values from the BST using an inorder traversal, which guarantees a sorted list of values. Then, we can use these sorted values to construct a new balanced BST.

```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:
        # Step 1: Inorder traversal to get sorted values
        inorder_values = []
        self.inorder_traversal(root, inorder_values)

        # Step 2: Build a balanced BST from the sorted values
        return self.build_balanced_bst(inorder_values)

    def inorder_traversal(self, node: TreeNode, values: list):
        if node:
            self.inorder_traversal(node.left, values)
            values.append(node.val)
            self.inorder_traversal(node.right, values)

    def build_balanced_bst(self, values: list) -> TreeNode:
        if not values:
            return None

        mid = len(values) // 2
        root = TreeNode(values[mid])
        root.left = self.build_balanced_bst(values[:mid])
        root.right = self.build_balanced_bst(values[mid+1:])

        return root

2. Optimal Approach (Inorder Traversal and Rebuild - Same as Naive)

Since the fundamental process is already quite efficient, with the inorder traversal taking O(N) time and building the balanced BST also taking O(N) time, there's no significantly more optimal approach in terms of time complexity. The naive approach is the optimal approach for this specific problem, focusing on simplicity and readability.

3. Detailed Explanation of Big(O) Run-time Analysis

• Inorder Traversal: The inorder_traversal function visits each node exactly once. Therefore, its time complexity is O(N), where N is the number of nodes in the BST.
• Build Balanced BST: The build_balanced_bst function recursively divides the list of sorted values and creates a balanced BST. Each node is visited and processed once. Therefore, its time complexity is also O(N).
• Overall: The balanceBST function calls inorder_traversal and build_balanced_bst sequentially. Thus, the overall time complexity is O(N) + O(N) = O(N).

4. Detailed Explanation of Big(O) Space Usage Analysis

• Inorder Traversal: The inorder_values list stores the sorted values of all nodes. Therefore, the space complexity is O(N).
• Build Balanced BST: The recursion stack of the build_balanced_bst function can go as deep as log(N) for a balanced tree. Therefore, the space complexity is O(log N).
• Overall: The space complexity is dominated by the inorder_values list, which is O(N). Thus, the overall space complexity is O(N).

5. Edge Cases and Handling

• Empty Tree: If the input root is None, the inorder_traversal function will not execute, and inorder_values will be an empty list. The build_balanced_bst function correctly handles the empty list by returning None, which is the correct result for an empty tree.
• Single Node Tree: If the input root has only one node, the inorder_traversal function will add the node's value to inorder_values. The build_balanced_bst function will then create a new tree with a single node, which is already balanced, and return it.
• Skewed Tree: If the input tree is heavily skewed (e.g., all nodes are on the left), the inorder_traversal function will still correctly extract the sorted values. The build_balanced_bst function will then create a balanced BST from these values, effectively rebalancing the tree.

These edge cases are handled correctly by the given approach.