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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Balance a Binary Search Tree

Number: 1285

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google, TikTok, Bloomberg

Problem Description

Given the root of a binary search tree, return a balanced binary search tree with the same node values. A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

Key Insights

  • Perform an in-order traversal to obtain a sorted list of node values.
  • Use the sorted list to reconstruct the BST by choosing the middle element as the root, ensuring balanced subtrees.
  • Recursively build left and right subtrees from the corresponding halves of the array.
  • Leveraging the BST's in-order property guarantees a sorted array, making the reconstruction straightforward.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of nodes, due to the in-order traversal and balanced BST construction. Space Complexity: O(n), for storing node values in an array and the recursion stack.

Solution

The problem is solved in two primary steps. First, perform an in-order traversal of the BST and store the node values in a sorted list. Then, build a balanced BST from this sorted list by recursively picking the middle element as the root. This ensures that the tree remains balanced because the heights of the left and right subtrees are kept as equal as possible.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # Node's value.
        self.left = left      # Left child.
        self.right = right    # Right child.

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        # In-order traversal to collect nodes in sorted order.
        def inorder(node):
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)
        
        sorted_vals = inorder(root)  # Sorted list of node values.
        
        # Recursively build balanced BST from the sorted list.
        def buildBST(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            node = TreeNode(sorted_vals[mid])
            node.left = buildBST(left, mid - 1)
            node.right = buildBST(mid + 1, right)
            return node
        
        return buildBST(0, len(sorted_vals) - 1)
← Back to All Questions