Balance a Binary Search Tree - Practice Coding Problems

Balance a Binary Search Tree - Problem

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.

Input & Output

Example 1 — Right Skewed Tree

$ Input: root = [1,null,2,null,3,null,4,null,null]

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

💡 Note: Original tree is completely right-skewed. After balancing, node 2 becomes root with 1 as left child and 3 as right child, with 4 as right child of 3.

Example 2 — Left Skewed Tree

$ Input: root = [2,1,3]

› Output: [2,1,3]

💡 Note: Tree is already balanced - depth difference between left and right subtrees is at most 1, so no changes needed.

Example 3 — Complex Unbalanced

$ Input: root = [1,null,2,null,3,null,4,null,5]

› Output: [3,2,4,1,null,null,5]

💡 Note: Completely unbalanced chain becomes balanced with 3 as root, 2 on left (with 1 as left child), and 4 on right (with 5 as right child).

Constraints

The number of nodes in the tree is in the range [1, 10⁴].
1 ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Unbalanced BST (right-skewed chain)

Process

Extract sorted values and rebuild balanced

Output

Perfectly balanced BST with same values

Key Takeaway

🎯 Key Insight: Use BST property - inorder traversal gives sorted array, then rebuild balanced from middle

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to use the BST property: inorder traversal gives sorted values. Extract sorted array via DFS, then use divide and conquer to build balanced tree by always choosing middle element as root. Best approach is DFS + Divide and Conquer. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Reconstruction	O(n! × n)	O(n)	Try all possible tree configurations and check if balanced
DFS Inorder + Divide and Conquer	O(n)	O(n)	Extract sorted values via DFS, then build balanced tree recursively

Brute Force Reconstruction — Algorithm Steps

Step 1: Extract all values from the BST
Step 2: Generate all possible BST structures
Step 3: Check each structure for balance property

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Values

Get all node values from original tree

Generate All BSTs

Create every possible BST arrangement

Check Balance

Test each tree for balance property

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int values[1000];
int valueCount = 0;

void inorder(struct TreeNode* node) {
    if (node) {
        inorder(node->left);
        values[valueCount++] = node->val;
        inorder(node->right);
    }
}

struct TreeNode* buildBalanced(int start, int end) {
    if (start > end) return NULL;
    int mid = start + (end - start) / 2;
    struct TreeNode* node = createNode(values[mid]);
    node->left = buildBalanced(start, mid - 1);
    node->right = buildBalanced(mid + 1, end);
    return node;
}

struct TreeNode* solution(struct TreeNode* root) {
    if (!root) return NULL;
    valueCount = 0;
    inorder(root);
    return buildBalanced(0, valueCount - 1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simplified parsing
    struct TreeNode* root = createNode(1);
    struct TreeNode* result = solution(root);
    printf("[%d]\n", result->val);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generating all possible BST structures takes factorial time, and checking balance takes O(n)

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for generated trees and recursion stack

⚡ Linearithmic Space

98.4K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler