We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Balance a Binary Search Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A balanced binary search tree (BST) ensures optimal search times for each node.
  • The in-order traversal of a BST yields a sorted array of its values.
  • By recursively building the tree from the sorted array, we can ensure balance.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we need to traverse all nodes. Space Complexity: O(n), for storing the in-order traversal of the nodes.

Solution

To balance a binary search tree, we can follow these steps:

  1. Perform an in-order traversal of the BST to retrieve the sorted values of the nodes.
  2. Use a recursive approach to build a balanced BST from the sorted array. The middle element of the array will be the root of the balanced BST, ensuring that the left and right subtrees have equal height whenever possible.

The data structures used in this approach include arrays to store the sorted values and tree nodes to construct the new balanced BST.

Code Solutions

def balanceBST(root):
    # Helper function to perform in-order traversal
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    # Helper function to construct a balanced BST from sorted array
    def sortedArrayToBST(nums):
        if not nums:
            return None
        mid = len(nums) // 2
        node = TreeNode(nums[mid])
        node.left = sortedArrayToBST(nums[:mid])
        node.right = sortedArrayToBST(nums[mid + 1:])
        return node
    
    sorted_values = inorder(root)
    return sortedArrayToBST(sorted_values)
← Back to All Questions