Balance A Binary Search Tree - Leetcode Solution

Problem statement:

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Solution:

The problem asks us to balance an unbalanced binary search tree while keeping its node values the same. We can solve this problem by following three steps:

1. Traverse the binary search tree and store the values of all its nodes in a sorted array using inorder traversal. This will result in a sorted array of all the node values.

2. Build a balanced binary search tree from the sorted array. We can do this by recursively selecting the middle element of the array and making it the root of the tree. Then, we can recursively build the left and the right subtrees of the root using the elements to the left and right of the middle element in the array.

3. Return the root of the balanced binary search tree.

Below is the implementation of the above steps:

# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        """
        Build a balanced binary search tree from a sorted array
        """
        if not nums:
            return None
        
        middle = len(nums) // 2
        root = TreeNode(nums[middle])
        root.left = self.sortedArrayToBST(nums[:middle])
        root.right = self.sortedArrayToBST(nums[middle+1:])
        
        return root
    
    def balanceBST(self, root: TreeNode) -> TreeNode:
        """
        Balance a binary search tree
        """
        # Traverse the binary search tree and store its node values in a sorted array
        def inorderTraversal(node):
            if not node:
                return []
            
            return inorderTraversal(node.left) + [node.val] + inorderTraversal(node.right)
        
        nums = inorderTraversal(root)
        
        # Build a balanced binary search tree from the sorted array
        return self.sortedArrayToBST(nums)

In the balanceBST function, we first traverse the input binary search tree using inorder traversal and store its node values in a sorted array nums. Then, we pass nums to the sortedArrayToBST function which builds a balanced binary search tree using the middle element as the root of the current subtree. Finally, we return the root of the balanced binary search tree.

Time complexity: The time complexity of the above solution is O(n log n) where n is the number of nodes in the binary search tree. The inorder traversal takes O(n) time and building a balanced binary search tree from a sorted array takes O(log n) time. Therefore total time complexity will be O(n log n).

Space complexity: The space complexity of the above solution is O(n) because we are storing all the node values in a sorted array. The recursive function calls will take additional space, but it will be O(log n) due to the balanced nature of the binary search tree. Therefore, the total space complexity will be O(n + log n) which can be simplified to O(n).

1