Log inSign up
mediumLeetCodeNot Started

Balance a Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

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.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 1 <= Node.val <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize that inorder traversal flattens any BST into sorted order in linear time.
  • Rebuild a perfectly balanced BST using divide-and-conquer binary splitting.
  • Understand the Day-Stout-Warren (DSW) O(1) space in-place rotation technique.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Rebalance an unbalanced or degenerate BST.
  • Convert arbitrary BST into a height-balanced BST.
  • Guaranteed BST properties on input.

Algorithmic Decision Tree:

  • If standard memory allowed -> Inorder traversal to array + recursive mid-point build (O(N) time, O(N) space).
  • If strict O(1) auxiliary space required -> Day-Stout-Warren (DSW) rotation algorithm.

Connected Patterns:

Convert Sorted Array to Binary Search TreeValidate Binary Search TreeFlatten Binary Tree to Linked List

1. Collect Values, Sort, and Rebuild

Intuition

Traverse the tree using any traversal (e.g. preorder or BFS) to extract all values into a list. Sort the list in O(N log N) time. Then recursively build the balanced BST by choosing the midpoint of the sorted range as the root.

When to apply: Naive baseline when unaware that BST inorder traversal is already sorted.

Algorithm

  1. Step 1: Traverse the tree using preorder or BFS to collect all values into an array.
  2. Step 2: Sort the array in O(N log N) time.
  3. Step 3: Define build(L, R): pick mid = (L + R) / 2 as root, recurse on [L, mid - 1] for left child, and [mid + 1, R] for right child.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11};
12
13class Solution {
14 void collect(TreeNode* root, vector<int>& vals) {
15 if (!root) return;
16 vals.push_back(root->val);
17 collect(root->left, vals);
18 collect(root->right, vals);
19 }
20 TreeNode* build(const vector<int>& vals, int l, int r) {
21 if (l > r) return nullptr;
22 int mid = l + (r - l) / 2;
23 TreeNode* root = new TreeNode(vals[mid]);
24 root->left = build(vals, l, mid - 1);
25 root->right = build(vals, mid + 1, r);
26 return root;
27 }
28public:
29 TreeNode* balanceBST(TreeNode* root) {
30 vector<int> vals;
31 collect(root, vals);
32 sort(vals.begin(), vals.end());
33 return build(vals, 0, (int)vals.size() - 1);
34 }
35};
36
37int main() {
38 TreeNode* root = new TreeNode(1);
39 root->right = new TreeNode(2);
40 root->right->right = new TreeNode(3);
41 root->right->right->right = new TreeNode(4);
42 Solution sol;
43 TreeNode* balanced = sol.balanceBST(root);
44 cout << "Balanced Root: " << balanced->val << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

2. Inorder Flattening to Node Array (Linear Time Rebuild)

Intuition

Because an inorder traversal of a BST already visits nodes in strictly increasing order, there is no need to call sort(). We perform an inorder traversal to populate an array of sorted tree nodes in O(N) time. Then, using binary divide-and-conquer, the middle node becomes the root, and we recursively build left and right children.

When to apply: The standard expected interview solution: clean, optimal O(N) runtime, simple to verify.

Algorithm

  1. Step 1: Perform inorder traversal: left -> root -> right; append each node to array nodes.
  2. Step 2: Define build(L, R): if L > R, return null.
  3. Step 3: mid = L + (R - L) / 2. root = nodes[mid].
  4. Step 4: root.left = build(L, mid - 1) and root.right = build(mid + 1, R). Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void inorder(TreeNode* root, vector<TreeNode*>& nodes) {
14 if (!root) return;
15 inorder(root->left, nodes);
16 nodes.push_back(root);
17 inorder(root->right, nodes);
18 }
19 TreeNode* build(const vector<TreeNode*>& nodes, int l, int r) {
20 if (l > r) return nullptr;
21 int mid = l + (r - l) / 2;
22 TreeNode* root = nodes[mid];
23 root->left = build(nodes, l, mid - 1);
24 root->right = build(nodes, mid + 1, r);
25 return root;
26 }
27public:
28 TreeNode* balanceBST(TreeNode* root) {
29 vector<TreeNode*> nodes;
30 inorder(root, nodes);
31 return build(nodes, 0, (int)nodes.size() - 1);
32 }
33};
34
35int main() {
36 TreeNode* root = new TreeNode(1);
37 root->right = new TreeNode(2);
38 root->right->right = new TreeNode(3);
39 Solution sol;
40 TreeNode* res = sol.balanceBST(root);
41 cout << "Optimal Root: " << res->val << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

3. Day-Stout-Warren (DSW) In-Place Rotations (O(1) Space)

Intuition

Phase 1: Create a sorted vine (a linked list where every node has only a right child). Traverse down: whenever a node has a left child, perform a standard right rotation. Phase 2: Compute number of nodes N, find m = 2^(floor(log2(N + 1))) - 1. Perform N - m left rotations to balance the leaves, then repeatedly perform m /= 2 left rotations on alternate nodes until the vine is compressed into a balanced binary search tree.

When to apply: When auxiliary memory is constrained to strict O(1) space (e.g., embedded memory environments).

Algorithm

  1. Step 1: Create dummy pseudo-root whose right child points to root.
  2. Step 2 (Vine phase): While current node has a left child, rotate right; otherwise move to right child.
  3. Step 3 (Count phase): Count total nodes N along the vine.
  4. Step 4 (Compression phase): Let m = 2^(floor(log2(N + 1))) - 1. Rotate left (N - m) times.
  5. Step 5: While m > 1, set m /= 2, rotate left m times. Return dummy.right.

Balance BST Execution Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Input BST skewed right: 1 -> 2 -> 3 -> 4
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Input BST skewed right: 1 -> 2 -> 3 -> 4. Inorder traversal yields [1, 2, 3, 4].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void rotateRight(TreeNode* grandParent, TreeNode* parent, TreeNode* leftChild) {
14 grandParent->right = leftChild;
15 parent->left = leftChild->right;
16 leftChild->right = parent;
17 }
18 void rotateLeft(TreeNode* grandParent, TreeNode* parent, TreeNode* rightChild) {
19 grandParent->right = rightChild;
20 parent->right = rightChild->left;
21 rightChild->left = parent;
22 }
23 int createVine(TreeNode* grandParent) {
24 int count = 0;
25 TreeNode* curr = grandParent->right;
26 while (curr) {
27 if (curr->left) {
28 TreeNode* leftChild = curr->left;
29 rotateRight(grandParent, curr, leftChild);
30 curr = leftChild;
31 } else {
32 count++;
33 grandParent = curr;
34 curr = curr->right;
35 }
36 }
37 return count;
38 }
39 void compress(TreeNode* grandParent, int count) {
40 TreeNode* curr = grandParent->right;
41 for (int i = 0; i < count; i++) {
42 TreeNode* rightChild = curr->right;
43 rotateLeft(grandParent, curr, rightChild);
44 grandParent = rightChild;
45 curr = grandParent->right;
46 }
47 }
48public:
49 TreeNode* balanceBST(TreeNode* root) {
50 TreeNode dummy(0);
51 dummy.right = root;
52 int n = createVine(&dummy);
53 int m = (1 << (int)log2(n + 1)) - 1;
54 compress(&dummy, n - m);
55 for (m = m / 2; m > 0; m /= 2) {
56 compress(&dummy, m);
57 }
58 return dummy.right;
59 }
60};
61
62int main() {
63 TreeNode* root = new TreeNode(1);
64 root->right = new TreeNode(2);
65 root->right->right = new TreeNode(3);
66 root->right->right->right = new TreeNode(4);
67 Solution sol;
68 TreeNode* res = sol.balanceBST(root);
69 cout << "DSW Balanced Root: " << res->val << endl;
70 return 0;
71}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Collect & SortO(N log N)O(N)Generic traversal + sort + binary rebuild.Comparison sorting overhead.
2.Inorder FlatteningO(N)O(N)Exploit BST inorder sorted property to eliminate sorting.Array memory allocation.
3.Day-Stout-Warren (DSW)OptimalO(N)O(1)In-place tree rotations converting tree to vine and back to balanced BST.None. Strictly optimal in time and space.

Common Pitfalls & Crucial Edge Cases

Calling sort() on the inorder traversal

Unnecessary O(N log N) work; an inorder traversal of a BST is ALREADY sorted.

Creating new node objects instead of reusing existing pointers

In languages with manual memory management, allocate cleanly or reuse existing node pointers.

Off-by-one errors in midpoint calculation

Use l + (r - l) / 2 to prevent potential integer overflow.

Crucial Edge Cases to Validate:

  • Already balanced BST — Returns an equally valid balanced BST.
  • Completely skewed BST (linked list) — Rebalances tree height from O(N) down to O(log N).
  • Single node tree — Returned unchanged as height is 0.
  • Two-node tree — Single root with one child is trivially balanced.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the core equivalence: 'Rebalancing a BST is identical to Convert Sorted Array to Balanced BST once we run an inorder traversal.'
  2. Offer the Day-Stout-Warren (DSW) algorithm as a follow-up answer when asked for O(1) auxiliary space optimization.
  3. Emphasize the logarithmic height reduction: transforms worst-case search time from O(N) to O(log N).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the Inorder Flattening approach run in O(N) instead of O(N log N)?

2.What algorithm balances an arbitrary BST in-place in O(N) time and O(1) auxiliary space?

3.What is the maximum allowed height difference between the left and right subtrees of any node in a height-balanced BST?

Back to DSA Sheet