Classic two-step problem: flatten by in-order traversal, then rebuild from the sorted middle.

Step 1 — in-order traversal → sorted array

For a BST, in-order traversal visits nodes in ascending order.

function inOrder(node, out) {
  if (!node) return;
  inOrder(node.left, out);
  out.push(node);
  inOrder(node.right, out);
}

Step 2 — build balanced BST from sorted array

Pick the middle as the root; recurse on the left and right halves.

function buildBalanced(arr, l, r) {
  if (l > r) return null;
  const mid = (l + r) >> 1;
  const node = arr[mid];
  node.left = buildBalanced(arr, l, mid - 1);
  node.right = buildBalanced(arr, mid + 1, r);
  return node;
}

function balanceBST(root) {
  const sorted = [];
  inOrder(root, sorted);
  return buildBalanced(sorted, 0, sorted.length - 1);
}

Why it works

• In-order gives a sorted list — preserving BST values.
• Picking the middle as root and recursing on halves ensures each subtree has roughly equal-sized halves → height balanced (⌈log₂(n+1)⌉).

Complexity

• Time: O(n) for traversal + O(n) for build = O(n).
• Space: O(n) for the array + O(log n) recursion stack.

Variants

• In-place without the extra array — use the Day–Stout–Warren algorithm (right-skewed vine → balanced tree). O(1) extra space.
• If you need strict AVL/RB, post-process to add balance metadata.

Edge cases

• Empty tree → null.
• Single node → unchanged.
• Already balanced → unchanged in shape, but a new structure (since you rebuild).

Interview framing

"Two steps. In-order traversal of a BST gives a sorted array of nodes; then I build a balanced BST by recursively picking the middle of the array as the root. That guarantees height ⌈log n⌉. O(n) time, O(n) space. If extra space were forbidden, I'd reach for Day–Stout–Warren — right-rotate to a vine, then balance with left rotations — O(1) space."