Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Inorder traversal of a binary search tree yields its values in sorted order. Once that order is known, choosing the middle value as a root splits the remaining values nearly equally, producing a balanced tree while preserving the search-tree property.

Approach

Collect all values by visiting each node's left subtree, then the node, then its right subtree. Python performs this recursively; JavaScript uses a traversal stack. Recursively rebuild each sorted interval by creating a node from its middle value and building its left and right halves. Empty intervals return no node. Return the new root; the solution allocates a new balanced tree rather than rotating or reusing the original nodes.

# 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 balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        nodes = []

        def dfs(node):
            if not node: return
            l = dfs(node.left)
            nodes.append(node.val)
            r = dfs(node.right)

        dfs(root)

        def build(l, r):
            if l > r: return
            mid = l + (r - l) // 2
            node = TreeNode(nodes[mid])
            node.left = build(l, mid - 1)
            node.right = build(mid + 1, r)
            return node
        
        return build(0, len(nodes) - 1)

Complexity analysis

For N nodes and original height H, inorder traversal and balanced reconstruction each take O(N) time. The sorted values use O(N) auxiliary space. Python uses O(H) recursion for traversal; JavaScript uses an O(H) explicit stack. Reconstruction uses O(log N) recursion, and the new tree is O(N) output. Python's initial traversal can exceed the default recursion limit on a legal 10000-node skewed tree unless the runner raises it sufficiently.