Balance a Binary Search Tree - Visualization

Binary Search Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

You are given an unbalanced Binary Search Tree (BST). Your task is to transform it into a height-balanced BST. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Your solution should not change the values of the nodes, only the structure of the tree to ensure it becomes balanced.

Examples❯

Input Tree Balanced BST Output Description
[1, null, 2, null, null, null, 3]
[2, 1, 3]
Original tree is right-skewed and unbalanced. In-order traversal: [1,2,3] → balanced BST is [2,1,3].
[3, 2, null, 1]
[2, 1, 3]
Input tree is left-heavy. In-order traversal: [1,2,3] → balanced BST root is 2 with 1 and 3 as children.
[10, 5, 15, 2, 7, null, 20]
[10, 5, 15, 2, 7, null, 20]
Already balanced BST. In-order traversal is sorted and tree height is balanced → output is unchanged.
[] [] Empty tree is trivially balanced; no action needed.
[7]
[7]
Single-node tree is inherently balanced; remains unchanged.

Solution❯

Understanding the Problem

A Binary Search Tree (BST) can become unbalanced if new nodes are inserted in sorted order or other skewed sequences. An unbalanced BST results in inefficient operations like search, insert, and delete, as it behaves more like a linked list with O(n) complexity. Our goal is to transform such an unbalanced BST into a balanced one — where the left and right subtrees of every node have roughly the same height. This ensures optimal time complexity for operations.

To do this, we use the property of BSTs that inorder traversal gives a sorted list of values. Once we have that list, we can rebuild a balanced BST by recursively selecting the middle element as root and constructing left and right subtrees from the left and right halves.

Step-by-Step Solution with Example

step 1: Perform Inorder Traversal

Given an unbalanced BST, the first step is to traverse it in inorder (left → root → right). For example, consider this tree: 


    1
           2
               3
                   4
                       5

Performing inorder traversal on this tree results in a sorted list: [1, 2, 3, 4, 5]

step 2: Build Balanced BST from Sorted List

The idea is to pick the middle element of the list as the root. For [1, 2, 3, 4, 5], the middle is 3. We make 3 the root.

- Left half [1, 2] becomes the left subtree.
- Right half [4, 5] becomes the right subtree.

Repeat the same process recursively:

  • Middle of [1, 2] is 2 → left child of 3
  • Middle of [4, 5] is 4 → right child of 3

Final tree: 


       3
     /       2     4
   /         1         5

This tree is balanced — the height difference between left and right subtrees at any node is minimal.

step 3: Use Recursion to Construct Subtrees

The building process is recursive:

  1. If the current list is empty, return null.
  2. Find the middle element and make it the current root.
  3. Recursively repeat for left and right halves.

Edge Cases

Empty Tree

If the input BST is empty (null root), there is nothing to balance. The algorithm should simply return null without errors.

Single Node Tree

A tree with just one node is already balanced. The algorithm will return the node as-is, as there are no children to reorganize.

Already Balanced Tree

If the BST is already balanced (e.g., built correctly with middle insertion logic), the algorithm will reconstruct it in the same balanced structure. This shows the solution is idempotent and safe to run multiple times.

Highly Skewed Tree

Trees where all nodes are to one side (left or right) — such as the example above — benefit the most. Balancing converts them from height O(n) to height O(log n).

Finally

This approach to balancing a BST is intuitive, efficient, and optimal for most real-world scenarios. It leverages the BST's sorted property and uses recursion to ensure that every subtree is built with a minimal height difference. This technique is widely used in self-balancing tree structures like AVL Trees and Red-Black Trees (though with additional constraints).

In summary, balance your BST by:

  • Collecting nodes using inorder traversal (sorted list)
  • Building a new BST using the middle element as root recursively

This guarantees efficient operation performance and maintains the original BST semantics.

Algorithm Steps❯

  1. Perform an inorder traversal of the BST to obtain a sorted array of node values.
  2. Recursively build a balanced BST from the sorted array:
  3. Find the middle element of the array and create a new node for it.
  4. Recursively repeat the process for the left subarray to build the left subtree and for the right subarray to build the right subtree.
  5. Return the newly constructed node as the root of the balanced BST.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 1000

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

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

void inorder(TreeNode* root, int* arr, int* index) {
    if (root == NULL) return;
    inorder(root->left, arr, index);
    arr[(*index)++] = root->val;
    inorder(root->right, arr, index);
}

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

TreeNode* balanceBST(TreeNode* root) {
    int arr[MAX_NODES];
    int index = 0;
    inorder(root, arr, &index);
    return buildBalancedBST(arr, 0, index - 1);
}

void printInorder(TreeNode* root) {
    if (root == NULL) return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

int main() {
    TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->right = createNode(3);
    root->right->right->right = createNode(4);

    TreeNode* balanced = balanceBST(root);
    printInorder(balanced);
    printf("\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...