LeetCode 1382 - Balance a Binary Search Tree

LeetCode Problem 1382

Difficulty: 🟡 Medium
Topics: Divide and Conquer, Greedy, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Here is a complete, detailed technical solution guide for LeetCode 1382 - Balance a Binary Search Tree, following all your formatting rules.

Problem Understanding

The problem asks us to take a binary search tree (BST) that may be unbalanced and produce a new BST that is balanced while preserving the original node values. A BST is balanced if, for every node, the depth of its left and right subtrees differ by at most 1.

The input is the root of a BST. Each node has an integer value, and the BST property holds: left child values are smaller than the node, right child values are larger. The output should be another BST containing the same values but restructured to be balanced. If multiple balanced BSTs are possible, any valid one is acceptable.

Constraints tell us that the tree can have up to 10,000 nodes, and values can range from 1 to 100,000. This indicates that a naive approach that repeatedly balances subtrees or performs costly tree rotations could be too slow.

Important edge cases include:

• Trees that are already balanced.
• Trees that are highly skewed (like a linked list).
• Trees with a single node.
• Trees where nodes have consecutive values (which can form long chains).

These cases ensure our algorithm correctly handles both trivial and extreme shapes of BSTs.

Approaches

Brute Force: A brute-force approach might repeatedly check subtree heights and rotate nodes to balance them, similar to how AVL trees rebalance after insertions. While this would eventually produce a balanced BST, it requires O(n log n) rotations per insertion and is unnecessarily complicated. Given 10,000 nodes, repeated height calculations could make this inefficient.

Optimal Approach: The key insight is that an inorder traversal of a BST produces nodes in sorted order. If we can extract the nodes into a sorted array, we can then build a balanced BST directly by recursively choosing the middle element as the root, left subarray for the left subtree, and right subarray for the right subtree. This guarantees the tree is height-balanced because each subtree receives approximately half of the nodes.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n) - O(n²)	O(n)	Repeated rotations or subtree rebalancing; inefficient for large trees
Optimal	O(n)	O(n)	Inorder traversal + recursive tree construction from sorted array

Algorithm Walkthrough

1. Inorder Traversal: Traverse the input BST in inorder and store node references in a list. This produces a sorted list of all nodes, preserving their values.
2. Recursive BST Construction: Define a recursive function that takes the start and end indices of the list segment. Choose the middle index as the root, recursively construct the left subtree from the left segment, and the right subtree from the right segment.
3. Base Case: If the segment is empty (start > end), return None.
4. Return Root: After the recursive calls finish, the top-level middle node becomes the root of the balanced BST.

Why it works: Selecting the middle element as root at each recursive step ensures that the left and right subtrees have nearly equal size. This produces a BST with minimal height and satisfies the balance condition. The inorder traversal guarantees that all node values maintain the BST property.

Python Solution

# 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
from typing import Optional, List

class Solution:
    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def inorder(node: Optional[TreeNode], nodes: List[TreeNode]) -> None:
            if not node:
                return
            inorder(node.left, nodes)
            nodes.append(node)
            inorder(node.right, nodes)

        def build_balanced(start: int, end: int) -> Optional[TreeNode]:
            if start > end:
                return None
            mid = (start + end) // 2
            root = nodes[mid]
            root.left = build_balanced(start, mid - 1)
            root.right = build_balanced(mid + 1, end)
            return root

        nodes: List[TreeNode] = []
        inorder(root, nodes)
        return build_balanced(0, len(nodes) - 1)

Implementation Walkthrough:

We first collect all nodes in sorted order using inorder. Then, build_balanced recursively selects the middle node of each segment to guarantee balance. The left and right child pointers are updated in-place for the original nodes to construct the new tree efficiently.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func balanceBST(root *TreeNode) *TreeNode {
    var nodes []*TreeNode

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        nodes = append(nodes, node)
        inorder(node.Right)
    }

    var buildBalanced func(start, end int) *TreeNode
    buildBalanced = func(start, end int) *TreeNode {
        if start > end {
            return nil
        }
        mid := (start + end) / 2
        root := nodes[mid]
        root.Left = buildBalanced(start, mid-1)
        root.Right = buildBalanced(mid+1, end)
        return root
    }

    inorder(root)
    return buildBalanced(0, len(nodes)-1)
}

Go Notes:

Slices store node references similar to Python lists. Recursive functions are defined as local variables. nil is used for empty subtrees. The logic is otherwise identical to the Python solution.

Worked Examples

Example 1:

Input: [1,null,2,null,3,null,4]

1. Inorder traversal: [1,2,3,4]
2. Build balanced BST: mid = 2 → root = 2

• Left segment [1] → root.left = 1

• Right segment [3,4] → mid = 3 → root.right = 3

• Left = nil, Right = 4

Output BST: [2,1,3,null,null,null,4]

Example 2:

Input: [2,1,3]

1. Inorder traversal: [1,2,3]
2. Build balanced BST: mid = 1 → root = 2

• Left segment [1] → root.left = 1
• Right segment [3] → root.right = 3

Output BST: [2,1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once in inorder and once during construction
Space	O(n)	List of nodes stores all n nodes, recursion stack is O(log n) in balanced tree

The approach efficiently constructs a balanced BST without redundant computations. The space for recursion is logarithmic due to balanced splitting, negligible compared to storing all nodes.

Test Cases

# Basic examples
assert Solution().balanceBST(TreeNode(2, TreeNode(1), TreeNode(3))).val == 2  # Already balanced
assert Solution().balanceBST(TreeNode(1, None, TreeNode(2, None, TreeNode(3)))).val == 2  # Skewed tree

# Single node
assert Solution().balanceBST(TreeNode(10)).val == 10

# Two nodes
assert Solution().balanceBST(TreeNode(1, None, TreeNode(2))).val in [1,2]

# Larger skewed tree
root = TreeNode(1)
curr = root
for i in range(2, 8):
    curr.right = TreeNode(i)
    curr = curr.right
balanced_root = Solution().balanceBST(root)
assert balanced_root.val in [4]  # Mid value

Test	Why
[2,1,3]	Already balanced, minimal adjustment
[1,null,2,null,3]	Skewed tree tests rebalancing
[10]	Single node, edge case
[1, null, 2]	Two nodes, checks correct mid selection
[1..7]	Larger skewed tree, tests recursion and balance

Edge Cases

Single Node: A tree with one node is trivially balanced. The algorithm returns the node itself, and recursion handles it by immediately returning for empty segments.

Highly Skewed Trees: Trees resembling a linked list (all nodes to the right or left) could cause naive balancing approaches to fail or stack overflow. The inorder extraction ensures we always have a sorted array, and the recursive construction guarantees logarithmic depth.

Duplicate Values: Although BSTs usually have unique values, the algorithm preserves original node identities. Even if duplicates existed, nodes are treated as objects, not just values, so balancing works correctly.

This approach is robust, efficient, and directly leverages BST properties to produce a balanced tree with minimal effort.