ProgramGuru

Balance a Binary Search Tree

Problem and examples

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.

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.

How it works

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.

  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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}

TreeNode* buildBalancedBST(const vector<int>& arr, int start, int end) {
    if (start > end) return nullptr;
    int mid = start + (end - start) / 2;
    TreeNode* node = new TreeNode(arr[mid]);
    node->left = buildBalancedBST(arr, start, mid - 1);
    node->right = buildBalancedBST(arr, mid + 1, end);
    return node;
}

TreeNode* balanceBST(TreeNode* root) {
    vector<int> arr;
    inorder(root, arr);
    return buildBalancedBST(arr, 0, arr.size() - 1);
}

void printInorder(TreeNode* root) {
    if (!root) return;
    printInorder(root->left);
    cout << root->val << " ";
    printInorder(root->right);
}

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

    TreeNode* balanced = balanceBST(root);
    printInorder(balanced);
    cout << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(root, arr):
    if root:
        inorder(root.left, arr)
        arr.append(root.val)
        inorder(root.right, arr)

def build_balanced_bst(sorted_arr):
    if not sorted_arr:
        return None
    mid = len(sorted_arr) // 2
    root = TreeNode(sorted_arr[mid])
    root.left = build_balanced_bst(sorted_arr[:mid])
    root.right = build_balanced_bst(sorted_arr[mid+1:])
    return root

def balance_bst(root):
    arr = []
    inorder(root, arr)
    return build_balanced_bst(arr)

if __name__ == '__main__':
    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4))))
    balanced = balance_bst(root)
    result = []
    inorder(balanced, result)
    print(result)

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class BalanceBST {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> inorderList = new ArrayList<>();
        inorder(root, inorderList);
        return buildBalancedBST(inorderList, 0, inorderList.size() - 1);
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    private TreeNode buildBalancedBST(List<Integer> list, int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = buildBalancedBST(list, start, mid - 1);
        node.right = buildBalancedBST(list, mid + 1, end);
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        root.right.right.right = new TreeNode(4);

        BalanceBST solver = new BalanceBST();
        TreeNode balanced = solver.balanceBST(root);
        printInorder(balanced);
    }

    public static void printInorder(TreeNode root) {
        if (root == null) return;
        printInorder(root.left);
        System.out.print(root.val + " ");
        printInorder(root.right);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorder(root, arr) {
    if (!root) return;
    inorder(root.left, arr);
    arr.push(root.val);
    inorder(root.right, arr);
}

function buildBalancedBST(sortedArr) {
    if (sortedArr.length === 0) return null;
    const mid = Math.floor(sortedArr.length / 2);
    const root = new TreeNode(sortedArr[mid]);
    root.left = buildBalancedBST(sortedArr.slice(0, mid));
    root.right = buildBalancedBST(sortedArr.slice(mid + 1));
    return root;
}

function balanceBST(root) {
    const arr = [];
    inorder(root, arr);
    return buildBalancedBST(arr);
}

const root = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3, null, new TreeNode(4))));
const balanced = balanceBST(root);
const result = [];
inorder(balanced, result);
console.log(result);

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorder(root *TreeNode, arr *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left, arr)
    *arr = append(*arr, root.Val)
    inorder(root.Right, arr)
}

func buildBalancedBST(arr []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := (start + end) / 2
    node := &TreeNode{Val: arr[mid]}
    node.Left = buildBalancedBST(arr, start, mid-1)
    node.Right = buildBalancedBST(arr, mid+1, end)
    return node
}

func balanceBST(root *TreeNode) *TreeNode {
    var arr []int
    inorder(root, &arr)
    return buildBalancedBST(arr, 0, len(arr)-1)
}

func printInorder(root *TreeNode) {
    if root == nil {
        return
    }
    printInorder(root.Left)
    fmt.Printf("%d ", root.Val)
    printInorder(root.Right)
}

func main() {
    root := &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 2}
    root.Right.Right = &TreeNode{Val: 3}
    root.Right.Right.Right = &TreeNode{Val: 4}

    balanced := balanceBST(root)
    printInorder(balanced)
    fmt.Println()
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type Node = Option<Rc<RefCell<TreeNode>>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Node,
    right: Node,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn inorder(node: &Node, values: &mut Vec<i32>) {
    if let Some(n) = node {
        inorder(&n.borrow().left, values);
        values.push(n.borrow().val);
        inorder(&n.borrow().right, values);
    }
}

fn build_balanced_bst(values: &[i32]) -> Node {
    if values.is_empty() {
        return None;
    }
    let mid = values.len() / 2;
    let root = TreeNode::new(values[mid]);
    root.borrow_mut().left = build_balanced_bst(&values[..mid]);
    root.borrow_mut().right = build_balanced_bst(&values[mid+1..]);
    Some(root)
}

fn balance_bst(root: Node) -> Node {
    let mut values = vec![];
    inorder(&root, &mut values);
    build_balanced_bst(&values)
}

fn print_inorder(node: &Node) {
    if let Some(n) = node {
        print_inorder(&n.borrow().left);
        print!("{} ", n.borrow().val);
        print_inorder(&n.borrow().right);
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().right = Some(TreeNode::new(2));
    root.borrow().right.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(3));
    root.borrow().right.as_ref().unwrap().borrow().right.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(4));

    let balanced = balance_bst(Some(root));
    print_inorder(&balanced);
    println!();
}

Kotlin implementation

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorder(root: TreeNode?, result: MutableList<Int>) {
    if (root != null) {
        inorder(root.left, result)
        result.add(root.value)
        inorder(root.right, result)
    }
}

fun buildBalancedBST(arr: List<Int>, start: Int, end: Int): TreeNode? {
    if (start > end) return null
    val mid = (start + end) / 2
    val node = TreeNode(arr[mid])
    node.left = buildBalancedBST(arr, start, mid - 1)
    node.right = buildBalancedBST(arr, mid + 1, end)
    return node
}

fun balanceBST(root: TreeNode?): TreeNode? {
    val list = mutableListOf<Int>()
    inorder(root, list)
    return buildBalancedBST(list, 0, list.size - 1)
}

fun printInorder(root: TreeNode?) {
    if (root != null) {
        printInorder(root.left)
        print("${root.value} ")
        printInorder(root.right)
    }
}

fun main() {
    val root = TreeNode(1)
    root.right = TreeNode(2)
    root.right!!.right = TreeNode(3)
    root.right!!.right!!.right = TreeNode(4)

    val balanced = balanceBST(root)
    printInorder(balanced)
    println()
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func inorder(_ root: TreeNode?, _ arr: inout [Int]) {
    guard let node = root else { return }
    inorder(node.left, &arr)
    arr.append(node.val)
    inorder(node.right, &arr)
}

func buildBalancedBST(_ arr: [Int], _ start: Int, _ end: Int) -> TreeNode? {
    if start > end { return nil }
    let mid = (start + end) / 2
    let node = TreeNode(arr[mid])
    node.left = buildBalancedBST(arr, start, mid - 1)
    node.right = buildBalancedBST(arr, mid + 1, end)
    return node
}

func balanceBST(_ root: TreeNode?) -> TreeNode? {
    var arr: [Int] = []
    inorder(root, &arr)
    return buildBalancedBST(arr, 0, arr.count - 1)
}

func printInorder(_ root: TreeNode?) {
    guard let node = root else { return }
    printInorder(node.left)
    print("\(node.val) ", terminator: "")
    printInorder(node.right)
}

let root = TreeNode(1)
root.right = TreeNode(2)
root.right?.right = TreeNode(3)
root.right?.right?.right = TreeNode(4)

let balanced = balanceBST(root)
printInorder(balanced)
print()

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorder(root: TreeNode | null, arr: number[]): void {
    if (!root) return;
    inorder(root.left, arr);
    arr.push(root.val);
    inorder(root.right, arr);
}

function buildBalancedBST(arr: number[]): TreeNode | null {
    if (arr.length === 0) return null;
    const mid = Math.floor(arr.length / 2);
    const node = new TreeNode(arr[mid]);
    node.left = buildBalancedBST(arr.slice(0, mid));
    node.right = buildBalancedBST(arr.slice(mid + 1));
    return node;
}

function balanceBST(root: TreeNode | null): TreeNode | null {
    const result: number[] = [];
    inorder(root, result);
    return buildBalancedBST(result);
}

const root = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3, null, new TreeNode(4))));
const balanced = balanceBST(root);
const output: number[] = [];
inorder(balanced, output);
console.log(output);