Problem Statement in English

You’re given the root of a binary search tree. Return a balanced binary search tree with the same node values.

Approach

Let’s say you express the values of the nodes in the binary search tree in an array. This array will be sorted since it’s a binary search tree, providing you perform an inorder traversal.

Now, if you split this array at the middle, the middle element will become the root of the balanced binary search tree.

The left half of the array will become the left subtree and the right half will become the right subtree.

You can apply this logic recursively to build the entire balanced binary search tree.

And we’re done!

Solution in Python


class Solution:
    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # inorder traversal to get a sorted view of node values
        # split at middle recursively

        view = []

        def inorder(node):
            if node.left:
                inorder(node.left)

            view.append(node.val)

            if node.right:
                inorder(node.right)

        inorder(root)

        def solve(arr):
            if not arr:
                return None
                
            if len(arr) == 1:
                return TreeNode(arr[0])

            mid = len(arr) // 2

            this = TreeNode(arr[mid])

            this.left = solve(arr[:mid])
            this.right = solve(arr[mid + 1:])

            return this

        return solve(view)

Complexity

  • Time: $O(n)$

  • Space: $O(n)$
    Since we’re using an array to store the node values.

And we are done.